分数: 266 分
问题陈述
高桥正在跳蚤市场经营一个摊位。他的摊位有卖 N 产品类型及其价格 i-第一个产品 (1 \leq i \leq N) is P_i 日元。假设每种产品的库存充足。
活动期间, M 顾客在高桥展位进行购买。的 j第客户 (1 \leq j \leq M) 已购买 Q_j 单位 T_j-第一个产品。
高桥最初有 S 日元现金。与客户的交易按照顺序一一处理,从 1st 客户。该交易与 j第一位客户收益如下,按此顺序:
- 计算销售额 X = P_{T_j} \times Q_j 日元。
- 作为客户的付款, X 日元被添加到高桥的手头现金中。
- 作为活动组织者的销售佣金, \lfloor X / 2 \rfloor 日元从他手头的现金中扣除。在这里, \lfloor a \rfloor 表示不超过实数的最大整数 a.
每笔交易中,佣金 \lfloor X / 2 \rfloor 最多为销售额 X,因此交易产生的现金净变化是非负的。因此,在交易过程中,手头现金永远不会变成负数。
与 M 客户已完成,高桥手头有多少日元?
约束
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq S \leq 10^9
- 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
- 1 \leq T_j \leq N (1 \leq j \leq M)
- 1 \leq Q_j \leq 10^4 (1 \leq j \leq M)
- 所有输入值均为整数
- 保证答案在 0 和 10^{13},包含在内
输入
N M S P_1 P_2 \ldots P_N T_1 Q_1 T_2 Q_2 \vdots T_M Q_M
- 第一行包含 N 代表产品类型数量, M 代表客户数量,以及 S 代表初始现金金额,以空格分隔。
- 第二行包含每种产品的价格 P_1, P_2, \ldots, P_N,用空格分隔。
- 在下面 M 行, j第行 (1 \leq j \leq M) 包含产品类型 T_j 购买者 j第客户及数量 Q_j,用空格分隔。
输出
在一行上打印所有交易完成后高桥拥有的现金金额。
样本输入 1
3 2 100 200 500 300 1 2 3 1
示例输出 1
450
示例输入 2
5 4 1000 150 300 99 500 1200 3 3 5 1 1 5 2 2
示例输出 2
2424
示例输入 3
6 5 0 1 9999 5000 3 7777 10000 2 10000 4 1 6 9999 1 1 5 5000
示例输出 3
119432503