A - お買い物の合計金額 解説 /

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

配点 : 200 点

テストケースに誤りがあったため、リジャッジを行いました。

問題文

高橋君はスーパーマーケットで買い物をしています。

高橋君は買い物かごに K 個の商品を入れました。それぞれの商品には値札がついており、i 番目 (1 \leq i \leq K) の商品の価格は L_i 円です。

このスーパーマーケットでは、レジで精算するときに、合計金額をある正の整数 M で割った余りに等しいポイントがもらえるキャンペーンを実施しています。

すなわち、すべての商品の価格の総和を S = L_1 + L_2 + \cdots + L_K としたとき、高橋君がもらえるポイントは S を M で割った余りです。なお、S が M の倍数であるときにもらえるポイントは 0 です。

高橋君がもらえるポイントを求めてください。

制約

  • 1 \leq K \leq 10^5
  • 1 \leq M \leq 10^9
  • 1 \leq L_i \leq 10^4 (1 \leq i \leq K)
  • 入力はすべて整数

入力

K M
L_1 L_2 \cdots L_K
  • 1 行目には、買い物かごに入れた商品の個数を表す整数 K と、ポイント計算に用いる正の整数 M が、スペース区切りで与えられる。
  • 2 行目には、各商品の価格を表す K 個の整数 L_1, L_2, \ldots, L_K が、スペース区切りで与えられる。

出力

高橋君がもらえるポイントを整数で 1 行に出力してください。

入力例 1

3 100
150 80 45

出力例 1

75

入力例 2

5 1000
1200 350 890 460 720

出力例 2

620

入力例 3

10 500000000
9999 8765 4321 5678 1234 7777 3333 6666 2222 8888

出力例 3

58883

Score : 200 pts

A mistake was made in the test case, requiring a re-judgment.

Problem Statement

Takahashi is shopping at a supermarket.

Takahashi has placed K items in his shopping basket. Each item has a price tag, and the price of the i-th item (1 \leq i \leq K) is L_i yen.

This supermarket is running a campaign where, at checkout, customers receive points equal to the remainder when the total amount is divided by a positive integer M.

That is, if the total sum of all item prices is S = L_1 + L_2 + \cdots + L_K, the points Takahashi receives are the remainder when S is divided by M. Note that if S is a multiple of M, the points received are 0.

Find the number of points Takahashi will receive.

Constraints

  • 1 \leq K \leq 10^5
  • 1 \leq M \leq 10^9
  • 1 \leq L_i \leq 10^4 (1 \leq i \leq K)
  • All inputs are integers

Input

K M
L_1 L_2 \cdots L_K
  • The first line contains an integer K representing the number of items in the shopping basket, and a positive integer M used for the point calculation, separated by a space.
  • The second line contains K integers L_1, L_2, \ldots, L_K representing the prices of each item, separated by spaces.

Output

Print the number of points Takahashi will receive as an integer on a single line.

Sample Input 1

3 100
150 80 45

Sample Output 1

75

Sample Input 2

5 1000
1200 350 890 460 720

Sample Output 2

620

Sample Input 3

10 500000000
9999 8765 4321 5678 1234 7777 3333 6666 2222 8888

Sample Output 3

58883