더치 페이

면접 대비

시간 제한1초메모리 제한1024 MB

요약

참석자들의 입장 시각과 퇴장 시각, 그리고 주문 시각과 가격이 주어질 때, 주문마다 그 시각에 있는 사람들이 가격을 나눠 낼 경우 한 사람이 내는 평균 금액을 구합니다.

문제

2학기 개강총회 날, KPSC 기획부 부장 캡틴은 부원들의 사기를 높이려고 특별한 회식 자리를 마련했다. 부원들이 하나둘 모이자 캡틴과 운영진은 참석자들의 입장 시각과 퇴장 시각을 기록했고, 음식 주문 내역도 빠짐없이 적었다.

캡틴이 모은 정보는 다음과 같다.

입장 및 퇴장 기록: $s\ e$ 형태로 주어지며, $s$ 시각에 입장해 식사를 하고 $e$ 시각에 퇴장했음을 뜻한다. 즉, $s$ 시각부터 $e$ 시각까지 주문된 음식을 모두 먹은 것으로 본다.
음식 주문 내역: $t\ p$ 형태로 주어지며, $t$ 시각에 가격이 $p$ 인 음식을 주문했음을 뜻한다. $t$ 시각에 $n$ 명이 있었다면 각자 $\displaystyle \frac{p}{n}$ 씩 낸다. 음식은 주문과 동시에 나오고, 나온 음식은 즉시 다 먹는다고 가정한다. 식당에 사람이 없을 때는 음식을 주문하지 않는다.

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

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

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

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