호텔

친구가 바닷가 도시에 호텔을 운영합니다. 성수기가 시작되면서 손님들의 예약 신청이 쏟아지자, 친구는 예약 시스템을 만드는 일을 여러분에게 부탁했습니다.

호텔에는 대여 가능한 방이 $n$개 있습니다. $i$번째 방은 손님을 받았을 때만 유지비 $c_i$가 들며, 최대 $p_i$명을 수용할 수 있습니다. 유지비는 수용 인원에 대해 단조롭습니다. 즉 어떤 방의 유지비는 그보다 더 적은 인원을 수용하는 방(수용 인원이 더 작은 방)의 유지비보다 결코 저렴하지 않습니다.

예약 시스템에는 여러 개의 신청이 들어옵니다. $j$번째 신청은 하루 동안 방 하나를 빌리는 대가로 지불할 금액 $v_j$와, 요구하는 방의 최소 수용 인원 $d_j$를 명시합니다. 각 신청은 방 하나에만 배정할 수 있고, 각 방은 신청 하나만 받을 수 있습니다. 배정되는 방은 반드시 그 신청의 최소 수용 인원 이상이어야 합니다. 친구는 최대 $o$개의 신청까지만 받기로 했습니다.

받은 신청 중 일부를 골라 배정했을 때 친구가 얻을 수 있는 최대 이익(대여로 받은 금액의 합에서 사용한 방들의 유지비 합을 뺀 값)을 구하세요.

첫 번째 줄에 세 정수 $n$, $m$, $o$가 주어집니다 ($1 \le n, m \le 500\,000$, $1 \le o \le \min(m, n)$). 각각 방의 수, 들어온 신청의 수, 받을 수 있는 신청의 최대 개수를 뜻합니다.

이어지는 $n$개의 줄에는 방의 정보가 주어지며, $i$번째 줄에는 두 정수 $c_i$, $p_i$가 주어집니다 ($1 \le c_i, p_i \le 10^9$). 각각 방의 유지비와 수용 인원을 뜻합니다.

이어지는 $m$개의 줄에는 신청의 정보가 주어지며, $j$번째 줄에는 두 정수 $v_j$, $d_j$가 주어집니다 ($1 \le v_j, d_j \le 10^9$). 각각 제시한 대여 금액과 요구하는 최소 수용 인원을 뜻합니다.

신청을 최대 $o$개까지 받아서 얻을 수 있는 최대 이익을 정수 하나로 출력합니다. 어떤 신청도 받지 않는 것이 가장 이득이라면 $0$을 출력합니다. 이익은 매우 커질 수 있습니다.