苏菲在她的帽子店里

苏菲在一家帽子店工作。她正试图装饰 $N$ 顶帽子，每顶帽子属于 $M$ 种不同款式（用 $1$ 到 $M$ 的整数表示）之一。每顶帽子也有一个不同的初始美观度 $S_j$。

相同款式的帽子具有一些共同的属性。所有属于款式 $i$ 的帽子都具有相同的最大美观度 $C_i$。此外，苏菲有足够的时间来设计 $K$ 个新的装饰。在设计装饰时，苏菲必须选择一种款式 $i$（以便她的装饰具有标准尺寸）。完成设计后，她会将这种装饰应用到款式 $i$ 的每顶帽子上，从而使属于该款式的每顶帽子的美观度增加 $F_i$。然而，款式 $i$ 的帽子的美观度永远不会超过 $C_i$。如果你试图提升一顶已经达到最大美观度的帽子，它的美观度将保持在该最大值。此外，苏菲可以选择为同一种款式设计多个装饰。苏菲希望最大化她所有帽子的总美观度。因此，在制作了 $K$ 个新装饰后，所有 $N$ 顶帽子的最大可能总美观度是多少？

输入格式

输入的第一行包含三个空格分隔的整数 $N$（$1 \le N \le 200\,000$）、$M$（$1 \le M \le 200\,000$）和 $K$（$1 \le K \le 10^9$），分别表示帽子的数量、帽子款式的数量以及苏菲可以设计的新装饰数量。

接下来的 $M$ 行，每行包含两个空格分隔的整数 $F_i$ 和 $C_i$，满足 $1 \le C_i \le 10^9$ 且 $1 \le F_i \le C_i$，其中 $F_i$ 表示款式 $i$ 的帽子每使用一个装饰所能提升的美观度，$C_i$ 表示该款式帽子的最大美观度。

接下来的 $N$ 行，每行包含两个空格分隔的整数 $T_j$（$1 \le T_j \le M$）和 $S_j$（$0 \le S_j \le C_{T_j}$），其中 $T_j$ 表示第 $j$ 顶帽子的款式，$S_j$ 表示第 $j$ 顶帽子的初始美观度。

输出格式

输出一行，包含一个整数，表示苏菲制作 $K$ 个新装饰后，所有 $N$ 顶帽子的最大可能总美观度。

样例

输入样例 1

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

输出样例 1

15