Hotel

Memory limit: 64 MB

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 rooms for rent in the hotel, the -th room costs your friend zlotys of upkeep (only if it is rented) and has a capacity of 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 () for one particular day and the minimal capacity of the requested room (). 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 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.

Input

The first line of the standard input contains three integers , , and (, ), 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 lines describe the rooms, with the -th of these lines containing two integers , representing the upkeep of the room in zlotys and the capacity of the room (). The next lines describe the offers, with the -th of these lines containing two integers , representing the offered rental price in zlotys and the minimal capacity of the requested room ().

You may assume that in test cases worth 40 points in total an additional inequality holds.

Output

The first and only line of the standard output should contain one integer equal to the maximum profit your friend can achieve accepting at most of the offers. Note that the profit might get big.

Example

For the input data:

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

the correct result is:

400

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

Task author: Jakub Pachocki.