时间限制： 2.0 秒

空间限制： 512 MB

题目描述

西西艾弗岛上共有 $n$ 间物流仓库，小 P 目前有 $m$ 件货物存放其中。为了获得至少为 $v$ 的现金，小 P 需要选取一些货物卖出。

已知货物信息如下，第 $i$ 件（$0 \le i < m$）货物：

• 存放在第 $t_i$ 间仓库中（$0 \le t_i < n$）；
• 价值为 $a_i$，即选择卖出该货物可获得 $a_i$ 的现金。

但在调货出库时也需要支付一些费用，对于第 $j$ 间（$0 \le j < n$）仓库：

• 只要调用了该仓库的货物（至少一件），就需要支付 $b_j$ 的基本费用；
• 如果调用了该仓库中共 $k$ 件货物，则还需要支付 $k \times c_j$ 的计件费用。

小 P 的最终目标是获得至少为 $v$ 的现金，即要求卖出的货物总价值减去总费用的结果大于或等于 $v$。 在满足该目标的前提下，试为小 P 规划一种花费最小的卖货方案。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 $n,m,v$。

接下来 $n$ 行输入仓库信息，其中第 $j$ 行（$0 \le j < n$）包含两个整数 $b_j$ 和 $c_j$。

接下来 $m$ 行输入货物信息，其中第 $i$ 行（$0 \le i < m$）包含两个整数 $a_i$ 和 $t_i$。

输出格式

输出到标准输出。

仅输出一个整数，表示完成目标前提下的最小花费。

2 3 15
2 1
3 2
10 0
20 1
15 0

4

样例 1 解释

最优方案：选取货物 $0$ 和 $2$，二者均在 $0$ 号仓库，总花费为 $2 + 2 \times 1 = 4$。

选取货物 $1$ 也刚好能满足要求（$20 - 3 - 1 \times 2 \ge 15$），但花费更多。

单独选取货物 $0$ 或 $2$ 均不能满足要求。

5 3 15
2 1
1 1
3 2
4 2
1 5
10 1
10 1
10 1

3

样例 2 解释

小 P 所有货物均存放在仓库 $1$ 中，任取两件货物卖出即可满足要求（$10 + 10 - 1 - 2 \times 1 \ge 15$）。

子任务

$30\%$ 的数据满足 $m \le 15$；

另有 $40\%$ 的数据满足 $a_i \le 20$；

全部的数据满足：

• $0 < n, m \le 1000$
• $0 < b_j, c_j \le 20$
• $0 < a_i \le 1000$
• $0 < v \le 10^{6}$ 且保证至少存在一种可满足要求的卖货方案。