A - Neighborhood Association Audit Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は町内会の会計係を務めています。町内会には共有の活動資金があり、日々の活動を通じてお金の出入りが発生します。

町内会では、新しい世帯が加入するたびに入会金を納めてもらうルールがあります。また、活動に必要な備品として飲料水を購入することがあります。飲料水は 1 本あたり一律 P 円です。

活動資金の初期残高は S 円でした。その後、時系列順に M 回のイベントが発生しました。各イベントは以下の 2 種類のいずれかです。

  • 入会イベント（e_i = 1）：新しい世帯が v_i 円の入会金を納め、活動資金に v_i 円が追加される。
  • 購入イベント（e_i = 2）：飲料水を v_i 本購入し、活動資金から v_i \times P 円が差し引かれる。

初期残高 S 円に対してすべてのイベントを記録どおりに順番に処理した場合の活動資金の最終残高を理論値と呼びます。

ある日、青木君が会計監査を行い、実際に残っている活動資金が R 円であることを確認しました。理論値と実際の残高 R の差額、すなわち（理論値）- R を求めてください。

制約

  • 1 \leq S \leq 10^9
  • 1 \leq P \leq 10^4
  • 0 \leq R \leq 10^{18}
  • 1 \leq M \leq 2 \times 10^5
  • e_i \in \{1, 2\}
  • e_i = 1 のとき、1 \leq v_i \leq 10^9（入会金は正の整数）
  • e_i = 2 のとき、1 \leq v_i \leq 10^5（購入本数は正の整数）
  • すべてのイベントを記録どおりに処理したとき、各イベント処理後の活動資金の残高は負にならない
  • （理論値）\geq R が保証される
  • 入力はすべて整数である

入力

S P R
M
e_1 v_1
e_2 v_2
\vdots
e_M v_M
  • 1 行目には、活動資金の初期残高を表す整数 S、飲料水 1 本あたりの価格を表す整数 P、実際の残高を表す整数 R が、スペース区切りで与えられる。
  • 2 行目には、イベントの回数を表す整数 M が与えられる。
  • 続く M 行にわたり、各イベントの情報が与えられる。
  • 2 + i 行目（1 \leq i \leq M）では、i 番目のイベントの種類を表す整数 e_i と、その値を表す整数 v_i がスペース区切りで与えられる。
  • e_i = 1 のとき入会イベントであり、v_i は入会金（円）を表す。
  • e_i = 2 のとき購入イベントであり、v_i は購入した飲料水の本数を表す。

出力

活動資金の理論値から実際の残高 R を引いた差額、すなわち（理論値）- R を 1 行で出力せよ。

入力例 1

1000 100 500
2
1 500
2 3

出力例 1

700

入力例 2

5000 150 5000
2
1 2000
2 10

出力例 2

500

入力例 3

100000 200 80000
5
1 50000
2 100
1 30000
2 200
2 50

出力例 3

30000

入力例 4

1000000000 10000 0
10
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

出力例 4

11000000000

入力例 5

1 1 0
1
2 1

出力例 5

0

Score : 233 pts

Problem Statement

Takahashi serves as the treasurer of a neighborhood association. The association has a shared activity fund, and money flows in and out through daily activities.

The neighborhood association has a rule that each new household must pay a membership fee when joining. Additionally, the association sometimes purchases drinking water as supplies needed for activities. Drinking water costs a flat rate of P yen per bottle.

The initial balance of the activity fund was S yen. After that, M events occurred in chronological order. Each event is one of the following two types:

  • Membership event (e_i = 1): A new household pays a membership fee of v_i yen, and v_i yen is added to the activity fund.
  • Purchase event (e_i = 2): v_i bottles of drinking water are purchased, and v_i \times P yen is deducted from the activity fund.

The final balance of the activity fund when all events are processed in order starting from the initial balance of S yen is called the theoretical value.

One day, Aoki conducted an audit and confirmed that the actual remaining activity fund is R yen. Find the difference between the theoretical value and the actual balance R, that is, (theoretical value) - R.

Constraints

  • 1 \leq S \leq 10^9
  • 1 \leq P \leq 10^4
  • 0 \leq R \leq 10^{18}
  • 1 \leq M \leq 2 \times 10^5
  • e_i \in \{1, 2\}
  • When e_i = 1, 1 \leq v_i \leq 10^9 (the membership fee is a positive integer)
  • When e_i = 2, 1 \leq v_i \leq 10^5 (the number of bottles purchased is a positive integer)
  • When all events are processed as recorded, the balance of the activity fund does not become negative after any event
  • It is guaranteed that (theoretical value) \geq R
  • All input values are integers

Input

S P R
M
e_1 v_1
e_2 v_2
\vdots
e_M v_M
  • The first line contains an integer S representing the initial balance of the activity fund, an integer P representing the price per bottle of drinking water, and an integer R representing the actual balance, separated by spaces.
  • The second line contains an integer M representing the number of events.
  • The following M lines provide the information for each event.
  • The (2 + i)-th line (1 \leq i \leq M) contains an integer e_i representing the type of the i-th event and an integer v_i representing its value, separated by a space.
  • When e_i = 1, it is a membership event, and v_i represents the membership fee (in yen).
  • When e_i = 2, it is a purchase event, and v_i represents the number of bottles of drinking water purchased.

Output

Output the difference obtained by subtracting the actual balance R from the theoretical value of the activity fund, that is, (theoretical value) - R, on a single line.

Sample Input 1

1000 100 500
2
1 500
2 3

Sample Output 1

700

Sample Input 2

5000 150 5000
2
1 2000
2 10

Sample Output 2

500

Sample Input 3

100000 200 80000
5
1 50000
2 100
1 30000
2 200
2 50

Sample Output 3

30000

Sample Input 4

1000000000 10000 0
10
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Sample Output 4

11000000000

Sample Input 5

1 1 0
1
2 1

Sample Output 5

0