/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君は、 N 個の植木鉢に毎朝水やりをしています。
各植木鉢 i （ 1 \leq i \leq N ）には、ちょうど R_i リットルの水が必要です。高橋君は今朝、じょうろに S リットルの水を汲みました。
すべての植木鉢に必要な水の合計は R_1 + R_2 + \cdots + R_N リットルです。高橋君は、すべての植木鉢にちょうど必要な量の水を与えたいと考えています。まずじょうろの水を使いますが、必要な水の合計に対して不足する場合は、不足分を近所の水道から購入して補います。水道からは 1 リットルあたり C 円で購入できます。じょうろの水だけで足りる場合は、水道から購入する必要はありません（じょうろに水が余っても問題ありません）。
水道から購入する水の代金（円）を求めてください。
制約
- 1 \leq N \leq 10^6
- 0 \leq S \leq 10^{12}
- 1 \leq C \leq 10^4
- 1 \leq R_i \leq 10^4 （ 1 \leq i \leq N ）
- 入力はすべて整数である。
入力
N S C R_1 R_2 \ldots R_N
- 1 行目には、植木鉢の数を表す整数 N 、じょうろに汲んだ水の量（リットル）を表す整数 S 、水道からの購入単価（円/リットル）を表す整数 C が、スペース区切りで与えられる。
- 2 行目には、各植木鉢 i に必要な水の量（リットル）を表す整数 R_1, R_2, \ldots, R_N が、スペース区切りで与えられる。
出力
水道から購入する水の代金（円）を整数で 1 行に出力せよ。じょうろの水だけですべての植木鉢の水やりをまかなえる場合は 0 を出力せよ。
入力例 1
3 5 2 3 2 4
出力例 1
8
入力例 2
3 10 3 2 3 1
出力例 2
0
入力例 3
10 20 100 5 8 3 7 6 4 9 2 1 10
出力例 3
3500
入力例 4
20 50 500 100 200 300 400 500 600 700 800 900 1000 150 250 350 450 550 650 750 850 950 1050
出力例 4
5725000
入力例 5
1 0 1 1
出力例 5
1
Score : 233 pts
Problem Statement
Takahashi waters N flower pots every morning.
Each flower pot i (1 \leq i \leq N) requires exactly R_i liters of water. This morning, Takahashi filled his watering can with S liters of water.
The total amount of water needed for all flower pots is R_1 + R_2 + \cdots + R_N liters. Takahashi wants to give each flower pot exactly the required amount of water. He will use the water from his watering can first, but if the total water needed exceeds what is in the watering can, he will purchase the shortage from a nearby water supply. Water can be purchased from the supply at C yen per liter. If the watering can alone has enough water, there is no need to purchase from the water supply (it is fine if water remains in the watering can).
Determine the cost (in yen) of water purchased from the water supply.
Constraints
- 1 \leq N \leq 10^6
- 0 \leq S \leq 10^{12}
- 1 \leq C \leq 10^4
- 1 \leq R_i \leq 10^4 (1 \leq i \leq N)
- All input values are integers.
Input
N S C R_1 R_2 \ldots R_N
- The first line contains the integer N representing the number of flower pots, the integer S representing the amount of water (in liters) filled in the watering can, and the integer C representing the unit price (yen per liter) of water from the supply, separated by spaces.
- The second line contains the integers R_1, R_2, \ldots, R_N representing the amount of water (in liters) required for each flower pot i, separated by spaces.
Output
Output the cost (in yen) of water purchased from the water supply as an integer on a single line. If the watering can alone is sufficient to water all the flower pots, output 0.
Sample Input 1
3 5 2 3 2 4
Sample Output 1
8
Sample Input 2
3 10 3 2 3 1
Sample Output 2
0
Sample Input 3
10 20 100 5 8 3 7 6 4 9 2 1 10
Sample Output 3
3500
Sample Input 4
20 50 500 100 200 300 400 500 600 700 800 900 1000 150 250 350 450 550 650 750 850 950 1050
Sample Output 4
5725000
Sample Input 5
1 0 1 1
Sample Output 5
1