A - フリーマーケットの売上管理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君はフリーマーケットに出店しています。彼のブースでは N 種類の商品を販売しており、 i 番目の商品 (1 \leq i \leq N) の価格は P_i 円です。各商品の在庫は十分にあるものとします。

イベント中、 M 人のお客さんが高橋君のブースで買い物をしました。 j 番目のお客さん (1 \leq j \leq M) は、 T_j 番目の商品を Q_j 個購入しました。

高橋君は最初 S 円の現金を持っています。お客さんとの取引は 1 番目のお客さんから順番に 1 人ずつ処理されます。 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 以下であるため、取引による現金の変化量は 0 以上です。したがって、取引の過程で手元の現金が負になることはありません。

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
  • 1 行目には、商品の種類数を表す N 、お客さんの人数を表す M 、初期の所持金を表す S が、スペース区切りで与えられる。
  • 2 行目には、各商品の価格 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
  • 続く M 行のうち j 行目 (1 \leq j \leq M) には、 j 番目のお客さんが購入した商品の種類 T_j と購入個数 Q_j が、スペース区切りで与えられる。

出力

すべての取引が完了した後の高橋君の所持金を 1 行で出力せよ。

入力例 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

Score : 266 pts

Problem Statement

Takahashi is running a booth at a flea market. His booth sells N types of products, and the price of the i-th product (1 \leq i \leq N) is P_i yen. Assume that the stock of each product is sufficient.

During the event, M customers made purchases at Takahashi's booth. The j-th customer (1 \leq j \leq M) purchased Q_j units of the T_j-th product.

Takahashi initially has S yen in cash. Transactions with customers are processed one by one in order, starting from the 1st customer. The transaction with the j-th customer proceeds as follows, in this order:

  1. Calculate the sales amount X = P_{T_j} \times Q_j yen.
  2. As payment from the customer, X yen is added to Takahashi's cash on hand.
  3. As a sales commission to the event organizer, \lfloor X / 2 \rfloor yen is deducted from his cash on hand. Here, \lfloor a \rfloor denotes the largest integer not exceeding the real number a.

In each transaction, the commission \lfloor X / 2 \rfloor is at most the sales amount X, so the net change in cash from a transaction is non-negative. Therefore, the cash on hand never becomes negative during the process of transactions.

After all transactions with the M customers have been completed, how many yen does Takahashi have on hand?

Constraints

  • 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)
  • All input values are integers
  • It is guaranteed that the answer is between 0 and 10^{13}, inclusive

Input

N M S
P_1 P_2 \ldots P_N
T_1 Q_1
T_2 Q_2
\vdots
T_M Q_M
  • The first line contains N representing the number of product types, M representing the number of customers, and S representing the initial amount of cash, separated by spaces.
  • The second line contains the prices of each product P_1, P_2, \ldots, P_N, separated by spaces.
  • In the following M lines, the j-th line (1 \leq j \leq M) contains the product type T_j purchased by the j-th customer and the quantity Q_j, separated by a space.

Output

Print on a single line the amount of cash Takahashi has after all transactions have been completed.

Sample Input 1

3 2 100
200 500 300
1 2
3 1

Sample Output 1

450

Sample Input 2

5 4 1000
150 300 99 500 1200
3 3
5 1
1 5
2 2

Sample Output 2

2424

Sample Input 3

6 5 0
1 9999 5000 3 7777 10000
2 10000
4 1
6 9999
1 1
5 5000

Sample Output 3

119432503