32762번 - 더치 페이 스페셜 저지

문제

2학기 개강총회 날, KPSC 기획부의 부장 캡틴은 부원들의 사기를 높이기 위해 특별한 회식 자리를 준비했다. 부원들이 하나둘 모여들자 캡틴과 운영진은 참여자들의 입장 시각과 퇴장 시각을 기록하였고, 음식 주문 내역까지 세심하게 기록하였다.

캡틴이 수집한 정보는 다음과 같다.

• 입장 및 퇴장 기록: $s\ e$ 형태로 주어지며 $s$ 시각에 입장해 식사를 하고 $e$ 시각에 퇴장하였음을 의미한다. 즉, $s$ 시각부터 $e$ 시각까지 주문한 음식들을 먹은 것으로 간주한다.
• 음식 주문 내역: $t\ p$ 형태로 주어지며 $t$시각에 가격이 $p$인 음식을 주문했음을 의미한다. $t$시각에 $n$명의 사람이 있었다면, 각각 $\displaystyle \frac{p}{n}$ 가격만큼 지불한다. 단, 주문과 동시에 음식이 나오며 나온 음식은 즉시 다 먹는다고 가정한다. 또한, 식당에 사람이 없을 때는 음식이 주문되지 않는다.

회식이 끝나고 계산하였을 캡틴의 1인당 평균 지불 금액을 출력하는 프로그램을 작성하여라.

입력

첫 번째 줄에 사람의 수 $N$과 음식 주문 기록 수 $M$이 공백으로 구분되어 주어진다.

그 다음 줄부터 $N$개의 줄에 걸쳐 입장 및 퇴장 기록 정보가 주어진다. 그중 $i$번째 줄에는 $i$번 사람의 입장 시각 $s_i$와 퇴장 시각 $e_i$이 공백으로 구분되어 주어진다.

그 다음 줄부터 $M$개의 줄에 걸쳐 음식 주문 내역 정보가 주어진다. 그중 $j$번째 줄에는 $j$번 음식이 주문된 시각 $t_j$와 가격 $p_j$가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 1인당 평균 지불 금액을 출력한다. 절대/상대 오차는 10ドル^{-4}$까지 허용한다.

제한

• 1ドル \le N \le 100,000円$
• 1ドル \le M \le 100,000円$
• 1ドル \le s_i \le e_i \lt 2^{31}$
• 1ドル \le t_j \lt 2^{31}$
• 1ドル \le p_j \le 10,000円$
• 입력으로 주어지는 수는 모두 정수이다.

노트