← 返回题目列表

AtCoder · awc0040_a

A. 跳蚤市场销售管理

中文机器翻译题面 查看原题

分数: 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第一位客户收益如下,按此顺序:

  1. 计算销售额 X = P_{T_j} \times Q_j 日元。
  2. 作为客户的付款, X 日元被添加到高桥的手头现金中。
  3. 作为活动组织者的销售佣金, \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