Problem H
Hatter's 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 \leq N \leq
200\, 000)$, $M \: (1 \leq
M \leq 200\, 000)$, and $K
\: (1 \leq K \leq 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 \leq C_i \leq 10^9$ and
$1 \leq F_i \leq 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 \leq T_j \leq M)$ and
$S_j \: (0 \leq S_j \leq
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.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 2 1 3 2 5 1 1 1 2 2 4 2 3 |
15 |
