B - Watering Duty Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君が住むマンションでは、N 人の住人が毎日 1 人ずつ交代で共用花壇の水やり当番を務めています。住人には 1 から N までの番号が付いています。

1 日目の当番は住人 S で、以降は番号順に S, S+1, \ldots, N, 1, 2, \ldots のように巡回します。すなわち、j 日目 (j = 1, 2, \ldots, D) の当番は住人 ((S - 1 + j - 1) \bmod N) + 1 です。

住人 i が当番の日には、花壇に A_i リットルの水をやります。住人 i が複数回当番になる場合でも、毎回同じ A_i リットルの水をやります。

1 日目から D 日目までの D 日間で花壇に使われる水の合計は何リットルか求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^{14}
  • 1 \leq S \leq N
  • 1 \leq A_i \leq 10^4
  • 入力はすべて整数である

入力

N D S
A_1 A_2 \ldots A_N
  • 1 行目には、住人の人数 N、日数 D、1 日目の当番の住人番号 S がスペース区切りで与えられる。
  • 2 行目には、住人 i (1 \leq i \leq N) が当番の日に使う水の量 A_i（リットル）が N 個、スペース区切りで与えられる。

出力

D 日間で使われる水の合計量（リットル）を整数として 1 行で出力せよ。

入力例 1

4 6 2
3 1 4 2

出力例 1

15

入力例 2

5 3 5
10 20 30 40 50

出力例 2

80

入力例 3

8 25 6
7 2 9 4 5 1 8 3

出力例 3

118

入力例 4

20 12345678901234 13
15 230 7 89 154 321 48 76 205 19 410 63 97 182 54 268 11 340 125 72

出力例 4

1719753070941911

入力例 5

1 100000000000000 1
10000

出力例 5

1000000000000000000

Score : 300 pts

Problem Statement

In the apartment building where Takahashi lives, N residents take turns watering the shared flower bed, with one person on duty each day. The residents are numbered from 1 to N.

The person on duty on day 1 is resident S, and from then on, duty rotates in order of their numbers: S, S+1, \ldots, N, 1, 2, \ldots. That is, the person on duty on day j (j = 1, 2, \ldots, D) is resident ((S - 1 + j - 1) \bmod N) + 1.

When resident i is on duty, they water the flower bed with A_i liters of water. Even if resident i is on duty multiple times, they use the same A_i liters of water each time.

Find the total amount of water (in liters) used on the flower bed over the D days from day 1 to day D.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^{14}
  • 1 \leq S \leq N
  • 1 \leq A_i \leq 10^4
  • All input values are integers.

Input

N D S
A_1 A_2 \ldots A_N
  • The first line contains the number of residents N, the number of days D, and the resident number S of the person on duty on day 1, separated by spaces.
  • The second line contains N space-separated values A_i (1 \leq i \leq N), the amount of water (in liters) that resident i uses when on duty.

Output

Output the total amount of water (in liters) used over the D days as a single integer on one line.

Sample Input 1

4 6 2
3 1 4 2

Sample Output 1

15

Sample Input 2

5 3 5
10 20 30 40 50

Sample Output 2

80

Sample Input 3

8 25 6
7 2 9 4 5 1 8 3

Sample Output 3

118

Sample Input 4

20 12345678901234 13
15 230 7 89 154 321 48 76 205 19 410 63 97 182 54 268 11 340 125 72

Sample Output 4

1719753070941911

Sample Input 5

1 100000000000000 1
10000

Sample Output 5

1000000000000000000