Your friend owns a hotel at the seaside in Gdynia. The summer season is just starting and he is overwhelmed by the number of offers from potential customers. He asked you for help in preparing a reservation system for the hotel.

There are n rooms for rent in the hotel, the i-th room costs your friend ci zlotys of upkeep (only if it is rented) and has a capacity of pi people. You may assume that the upkeep of a room is never cheaper than the upkeep of any smaller room, that is, of any room which can hold a smaller number of people. The reservation system will be receiving multiple offers, each of them specifying the amount of zlotys for rental of any room (vj ) for one particular day and the minimal capacity of the requested room (dj ). For each offer, only a single room can be rented. And conversely: each room can accommodate only a single offer. Your friend has decided not to accept more than o offers.

Knowing you are a skilled programmer, your friend asked you to implement the part of the system which finds the maximum profit (total income from renting out rooms minus their upkeep) he can make by accepting some of the offers.

입력

• The first line of the standard input contains three integers n, m, and o (1 <= n, m <= 500 000, 1 <= o <= min(m, n)), denoting the number of rooms in the hotel, the number of offers received and the maximum number of offers your friend is willing to accept.
• The next n lines describe the rooms, with the i-th of these lines containing two integers ci , pi representing the upkeep of the room in zlotys and the capacity of the room (1 <= ci , pi <= 10^9).
• The next m lines describe the offers, with the j-th of these lines containing two integers vj , dj representing the offered rental price in zlotys and the minimal capacity of the requested room (1 <= vj , dj <= 10^9).

출력

입출력 예

입력

3 2 2
150 2
400 3
100 2
200 1
700 3

출력

400

Explanation of the example: Your friend can accept both offers, renting out rooms number 2 and 3

출처:ceoi 2011