Problem I
Hatter's Hat Shop

Sophie at her hat shop

Sophie works at a hat shop. She is trying to decorate $N$ hats, where each hat belongs to one of $M$ different designs (denoted by an integer from $1$ to $M$). Each hat also starts with a different amount of starting beauty $S_j$.

Hats of the same design share some properties. All hats belonging to the same design $i$ have the same maximum beauty $C_i$. Moreover, Sophie has enough time to devise $K$ new decorations. When designing a decoration, Sophie must pick a design $i$ (so that her decorations have standard measurements). After finishing her design, she then applies this decoration to each hat of design $i$, resulting in each hat belonging to that design having its beauty increased by an amount $F_i$. However, a hat of design $i$ will never be able to be more beautiful than $C_i$. In the case you try to improve a hat already at peak beauty, the hat simply remains at that peak. Moreover, Sophie can choose to make multiple decorations for the same hat design. Sophie wants to maximize the total beauty of her hats. Thus, after creating $K$ new decorations, what is the maximum possible sum of the beauty of all $N$ hats?

Input

The first line of input contains three space separated integers $N(1\le N\le 200000)$, $M(1\le M\le 200000)$, and $K(1\le K\le {10}^9)$, denoting the number of hats, the number of hat designs, and the number of decorations Sophie can devise, respectively.
Each of the next $M$ lines contains two space separated integers $F_i$ and $C_i$ such that $1\le C_i\le {10}^9$ and $1\le F_i\le C_i$, where $F_i$ represents how much hats of design $i$ are improved by one decoration and $C_i$ represents the max beauty of this hat design.
Each of the next $N$ lines contains two space separated integers $T_j(1\le T_j\le M)$ and $S_j(0\le S_j\le C_{T_j})$, where $T_j$ represents the design of hat $j$ and $S_j$ represents the amount of starting beauty of hat $j$.

Output

Output one line containing a single number, representing the maximum possible sum of the beauty of all $N$ hats after Sophie creates $K$ new decorations.

4 2 2
1 3
2 5
1 1
1 2
2 4
2 3

15