A - 荷物の仕分け

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

配点 : 233 点

問題文

高橋君は配送センターで荷物の仕分け作業を担当しています。このセンターでは、届いた荷物を配送予定の年月ごとに振り分けて管理しています。

今月は Y 年 M 月です。高橋君のもとに N 個の荷物が届きました。i 番目 (1 \leq i \leq N) の荷物には、受付年月 A_i 年 B_i 月、配送予定年月 P_i 年 Q_i 月、重量 C_i グラムが記載されています。

高橋君は、これらの荷物のうち配送予定年月が今月のものと翌月のものをそれぞれ振り分け、各月の合計重量を求めたいと考えています。なお、受付年月は荷物に記載されていますが、振り分けには一切使用しません。

ここで、ある年月の翌月とは次のように定めます。

  • その月が 12 月の場合、翌月は翌年の 1 月とする。例えば 2025 年 12 月の翌月は 2026 年 1 月である。
  • それ以外の場合、翌月はその年の次の月とする。例えば 2025 年 3 月の翌月は 2025 年 4 月である。

振り分けルールは次の通りです。

  • 配送予定年月 P_i 年 Q_i 月が Y 年 M 月と一致する荷物は、今月分とする。
  • 配送予定年月 P_i 年 Q_i 月が Y 年 M 月の翌月(上記の定義に従う)と一致する荷物は、翌月分とする。
  • 上記のいずれにも該当しない荷物は無視する(合計重量に加えない)。

今月分の合計重量と翌月分の合計重量をそれぞれ求めてください。該当する荷物が 1 つもない月の合計重量は 0 とします。

制約

  • 1 \leq N \leq 100
  • 2000 \leq Y \leq 2100
  • 1 \leq M \leq 12
  • 2000 \leq A_i \leq 2100 (1 \leq i \leq N)
  • 1 \leq B_i \leq 12 (1 \leq i \leq N)
  • 2000 \leq P_i \leq 2100 (1 \leq i \leq N)
  • 1 \leq Q_i \leq 12 (1 \leq i \leq N)
  • 配送予定年月 P_i 年 Q_i 月は、受付年月 A_i 年 B_i 月と同じか、その翌月(上記の定義に従う)のいずれかである。(1 \leq i \leq N)
  • 1 \leq C_i \leq 10000 (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N Y M
A_1 B_1 P_1 Q_1 C_1
A_2 B_2 P_2 Q_2 C_2
\vdots
A_N B_N P_N Q_N C_N
  • 1 行目には、荷物の個数 N 、今月の年 Y 、今月の月 M が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、i 番目の荷物の受付年 A_i 、受付月 B_i 、配送予定年 P_i 、配送予定月 Q_i 、重量 C_i が、スペース区切りで与えられる。

出力

今月分の合計重量と翌月分の合計重量を、スペース区切りで 1 行に出力せよ。該当する荷物が 1 つもない月の合計重量は 0 とすること。末尾に改行を出力すること。


入力例 1

3 2025 3
2025 3 2025 3 500
2025 3 2025 4 300
2025 2 2025 2 1000

出力例 1

500 300

入力例 2

4 2025 6
2025 1 2025 1 200
2025 1 2025 2 300
2025 3 2025 3 400
2025 3 2025 4 500

出力例 2

0 0

入力例 3

10 2025 12
2025 12 2025 12 100
2025 12 2026 1 200
2025 11 2025 12 300
2025 11 2025 11 150
2025 12 2026 1 400
2026 1 2026 1 500
2026 1 2026 2 250
2025 10 2025 10 600
2025 10 2025 11 700
2025 12 2025 12 350

出力例 3

750 1100

入力例 4

20 2050 7
2050 7 2050 7 100
2050 7 2050 8 200
2050 6 2050 7 300
2050 6 2050 6 400
2050 7 2050 8 500
2050 8 2050 8 150
2050 8 2050 9 250
2050 7 2050 7 350
2050 5 2050 5 1000
2050 5 2050 6 2000
2050 7 2050 8 700
2050 6 2050 7 800
2050 7 2050 7 450
2050 8 2050 8 300
2050 9 2050 9 600
2050 7 2050 8 900
2050 6 2050 6 550
2050 6 2050 7 650
2050 8 2050 8 120
2050 7 2050 7 210

出力例 4

2860 2870

入力例 5

1 2000 1
2000 1 2000 1 1

出力例 5

1 0

Score : 233 pts

Problem Statement

Takahashi is in charge of sorting packages at a delivery center. At this center, incoming packages are sorted and managed by their scheduled delivery year and month.

The current month is year Y, month M. Takahashi has received N packages. The i-th package (1 \leq i \leq N) has the following information: reception year-month A_i year B_i month, scheduled delivery year-month P_i year Q_i month, and weight C_i grams.

Takahashi wants to sort these packages into those whose scheduled delivery year-month is the current month and those whose scheduled delivery year-month is the next month, and calculate the total weight for each month. Note that although the reception year-month is written on the packages, it is not used for sorting at all.

The next month of a given year-month is defined as follows:

  • If the month is December (12), the next month is January (1) of the following year. For example, the next month of December 2025 is January 2026.
  • Otherwise, the next month is the next month of the same year. For example, the next month of March 2025 is April 2025.

The sorting rules are as follows:

  • If the scheduled delivery year-month P_i year Q_i month matches year Y month M, the package is classified as this month's.
  • If the scheduled delivery year-month P_i year Q_i month matches the next month of year Y month M (according to the definition above), the package is classified as next month's.
  • Packages that do not fall into either of the above categories are ignored (not added to the total weight).

Find the total weight for this month's packages and the total weight for next month's packages, respectively. If there are no applicable packages for a month, the total weight for that month is 0.

Constraints

  • 1 \leq N \leq 100
  • 2000 \leq Y \leq 2100
  • 1 \leq M \leq 12
  • 2000 \leq A_i \leq 2100 (1 \leq i \leq N)
  • 1 \leq B_i \leq 12 (1 \leq i \leq N)
  • 2000 \leq P_i \leq 2100 (1 \leq i \leq N)
  • 1 \leq Q_i \leq 12 (1 \leq i \leq N)
  • The scheduled delivery year-month P_i year Q_i month is either the same as the reception year-month A_i year B_i month, or the next month (according to the definition above). (1 \leq i \leq N)
  • 1 \leq C_i \leq 10000 (1 \leq i \leq N)
  • All input values are integers.

Input

N Y M
A_1 B_1 P_1 Q_1 C_1
A_2 B_2 P_2 Q_2 C_2
\vdots
A_N B_N P_N Q_N C_N
  • The first line contains the number of packages N, the current year Y, and the current month M, separated by spaces.
  • The following N lines, where the i-th line (1 \leq i \leq N), contains the reception year A_i, reception month B_i, scheduled delivery year P_i, scheduled delivery month Q_i, and weight C_i of the i-th package, separated by spaces.

Output

Print the total weight for this month and the total weight for next month on a single line, separated by a space. If there are no applicable packages for a month, the total weight for that month should be 0. Print a newline at the end.


Sample Input 1

3 2025 3
2025 3 2025 3 500
2025 3 2025 4 300
2025 2 2025 2 1000

Sample Output 1

500 300

Sample Input 2

4 2025 6
2025 1 2025 1 200
2025 1 2025 2 300
2025 3 2025 3 400
2025 3 2025 4 500

Sample Output 2

0 0

Sample Input 3

10 2025 12
2025 12 2025 12 100
2025 12 2026 1 200
2025 11 2025 12 300
2025 11 2025 11 150
2025 12 2026 1 400
2026 1 2026 1 500
2026 1 2026 2 250
2025 10 2025 10 600
2025 10 2025 11 700
2025 12 2025 12 350

Sample Output 3

750 1100

Sample Input 4

20 2050 7
2050 7 2050 7 100
2050 7 2050 8 200
2050 6 2050 7 300
2050 6 2050 6 400
2050 7 2050 8 500
2050 8 2050 8 150
2050 8 2050 9 250
2050 7 2050 7 350
2050 5 2050 5 1000
2050 5 2050 6 2000
2050 7 2050 8 700
2050 6 2050 7 800
2050 7 2050 7 450
2050 8 2050 8 300
2050 9 2050 9 600
2050 7 2050 8 900
2050 6 2050 6 550
2050 6 2050 7 650
2050 8 2050 8 120
2050 7 2050 7 210

Sample Output 4

2860 2870

Sample Input 5

1 2000 1
2000 1 2000 1 1

Sample Output 5

1 0
B - 合格ラインの日々

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

配点 : 300 点

問題文

高橋君は N 日間にわたる試験期間を過ごしています。毎日 1 つの試験があり、i 日目 (1 \leq i \leq N) の試験における高橋君の点数は A_i 点です。

高橋君は毎日、試験が終わった後に、1 日目からその日までの全試験の平均点を計算します。その日の点数が平均点以上であれば、「今日は調子が良かった」と感じ、満足します。

具体的には、1 日目から k 日目までの平均点を

M_k = \frac{A_1 + A_2 + \dots + A_k}{k}

としたとき、A_k \geq M_k を満たす日 k に高橋君は満足します。これは k \cdot A_k \geq A_1 + A_2 + \dots + A_k と同値です。

なお、1 日目は平均点が A_1 自身となるため、高橋君は必ず満足します。

N 日間の試験の点数が与えられたとき、高橋君が満足する日の数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \dots A_N
  • 1 行目には、試験期間の日数を表す整数 N が与えられる。
  • 2 行目には、各日の試験の点数を表す N 個の整数 A_1, A_2, \dots, A_N が空白区切りで与えられる。

出力

高橋君が満足する日の数を 1 行で出力してください。


入力例 1

5
60 80 50 70 90

出力例 1

4

入力例 2

5
100 50 30 20 10

出力例 2

1

入力例 3

10
50 60 40 70 30 80 20 90 10 100

出力例 3

6

入力例 4

20
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50

出力例 4

20

入力例 5

1
0

出力例 5

1

Score : 300 pts

Problem Statement

Takahashi is going through an exam period lasting N days. There is one exam each day, and Takahashi's score on the exam on day i (1 \leq i \leq N) is A_i points.

Every day, after the exam is over, Takahashi calculates the average score of all exams from day 1 through that day. If that day's score is at least the average, he feels "I did well today" and is satisfied.

Specifically, letting the average score from day 1 through day k be

M_k = \frac{A_1 + A_2 + \dots + A_k}{k}

Takahashi is satisfied on day k if A_k \geq M_k. This is equivalent to k \cdot A_k \geq A_1 + A_2 + \dots + A_k.

Note that on day 1, the average is A_1 itself, so Takahashi is always satisfied.

Given the exam scores over the N days, find the number of days on which Takahashi is satisfied.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \dots A_N
  • The first line contains an integer N representing the number of days in the exam period.
  • The second line contains N integers A_1, A_2, \dots, A_N separated by spaces, representing the exam scores for each day.

Output

Print the number of days on which Takahashi is satisfied, on a single line.


Sample Input 1

5
60 80 50 70 90

Sample Output 1

4

Sample Input 2

5
100 50 30 20 10

Sample Output 2

1

Sample Input 3

10
50 60 40 70 30 80 20 90 10 100

Sample Output 3

6

Sample Input 4

20
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50

Sample Output 4

20

Sample Input 5

1
0

Sample Output 5

1
C - 階段を登る方法

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

配点 : 366 点

問題文

高橋君は N 段の階段を登ろうとしています。

各段には下から順に 1 から N の番号が付けられています。高橋君は地面(0 段目)からスタートし、ちょうど N 段目に到達することを目指します。

高橋君は1回の移動で 1 段、2 段、または 3 段上に登ることができます。すなわち、現在 k 段目にいるとき、k+1 段目、k+2 段目、k+3 段目のいずれかへ直接移動できます(ただし N 段目を超える移動はできません)。このとき、移動先の段にのみ止まり、間にある段には止まりません。

一部の段は塗装中であり、塗装中の段を移動先に選ぶことはできません(止まることができません)。ただし、塗装中の段を間に挟んで飛び越える移動は可能です。0 段目(地面)は塗装中ではなく、常に止まることができます。

各段が塗装中かどうかは長さ N の文字列 S で与えられます。S の i 文字目(1 \leq i \leq N)が . のとき i 段目は塗装中でなく止まることができ、# のとき i 段目は塗装中で止まることができません。

高橋君が 0 段目からちょうど N 段目に到達するまでの登り方が何通りあるか、10^9 + 7 で割った余りを求めてください。

ここで、2つの登り方が異なるとは、移動先として止まった段の列(N 段目を含む)が異なることを指します。

制約

  • 1 \leq N \leq 10^5
  • N は整数
  • S は . と # のみからなる長さ N の文字列
  • S の N 文字目は . である(N 段目は塗装中でないことが保証される)

入力

N
S
  • 1 行目には、階段の段数を表す整数 N が与えられる。
  • 2 行目には、各段の状態を表す長さ N の文字列 S が与えられる。S の i 文字目は i 段目の状態に対応し、. なら塗装中でなく止まることができ、# なら塗装中で止まることができない。なお、0 段目(地面)の情報は S に含まれず、0 段目は常に止まることができる。

出力

高橋君が 0 段目から N 段目に到達するための登り方の総数を 10^9 + 7 で割った余りを 1 行で出力せよ。到達する方法が存在しない場合は 0 を出力せよ。


入力例 1

5
..#..

出力例 1

5

入力例 2

10
..#...#...

出力例 2

34

入力例 3

20
#.#.............#...

出力例 3

5849

Score : 366 pts

Problem Statement

Takahashi is trying to climb a staircase with N steps.

Each step is numbered from 1 to N from the bottom. Takahashi starts from the ground (step 0) and aims to reach exactly step N.

In one move, Takahashi can climb 1 step, 2 steps, or 3 steps upward. That is, if he is currently on step k, he can move directly to step k+1, step k+2, or step k+3 (however, he cannot move beyond step N). When moving, he only stops on the destination step and does not stop on any steps in between.

Some steps are being painted, and Takahashi cannot choose a painted step as a destination (he cannot stop on it). However, it is possible to jump over a painted step that lies in between. Step 0 (the ground) is not being painted and can always be stopped on.

Whether each step is being painted is given by a string S of length N. If the i-th character (1 \leq i \leq N) of S is ., then step i is not being painted and can be stopped on; if it is #, then step i is being painted and cannot be stopped on.

Find the number of ways Takahashi can climb from step 0 to exactly step N, modulo 10^9 + 7.

Here, two ways of climbing are considered different if the sequences of steps stopped on (including step N) are different.

Constraints

  • 1 \leq N \leq 10^5
  • N is an integer
  • S is a string of length N consisting only of . and #
  • The N-th character of S is . (it is guaranteed that step N is not being painted)

Input

N
S
  • The first line contains an integer N representing the number of steps.
  • The second line contains a string S of length N representing the state of each step. The i-th character of S corresponds to the state of step i: . means it is not being painted and can be stopped on, # means it is being painted and cannot be stopped on. Note that the information about step 0 (the ground) is not included in S, and step 0 can always be stopped on.

Output

Output in one line the total number of ways Takahashi can climb from step 0 to step N, modulo 10^9 + 7. If there is no way to reach step N, output 0.


Sample Input 1

5
..#..

Sample Output 1

5

Sample Input 2

10
..#...#...

Sample Output 2

34

Sample Input 3

20
#.#.............#...

Sample Output 3

5849
D - 照明の切り替え

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

配点 : 400 点

問題文

高橋君はイベント会場に N 行 M 列のグリッド状に照明を設置しました。各照明には初期の明るさが設定されており、i 行 j 列目の照明の初期の明るさは B_{i,j} です。

高橋君はイベントの演出として、照明の明るさを調整することにしました。各照明にはスイッチが付いており、スイッチを 1 回押すごとに、その照明の状態が「通常モード」と「強調モード」の間で切り替わります。最初、すべての照明は通常モードです。

高橋君は Q 回のスイッチ操作を順に行います。k 回目 (1 \leq k \leq Q) の操作では、入力で指定された長方形領域、すなわち左上が (r1_k, c1_k) 、右下が (r2_k, c2_k) である領域内のすべての照明のスイッチを 1 回ずつ押します。ここで、照明 (i, j) がこの長方形領域内に含まれるとは、r1_k \leq i \leq r2_k かつ c1_k \leq j \leq c2_k を満たすことを意味します。

Q 回の操作がすべて終わった後、各照明の最終的な明るさは、その照明のモードによって以下のように決まります。

  • 強調モードの照明(スイッチが押された回数が奇数回):明るさは 2 \times B_{i,j}
  • 通常モードの照明(スイッチが押された回数が偶数回。0 回も偶数回に含む):明るさは B_{i,j}

すべての操作が終わった後の、会場全体の照明の明るさの合計を求めてください。

制約

  • 1 \leq N \leq 1500
  • 1 \leq M \leq 1500
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq B_{i,j} \leq 10^4
  • 1 \leq r1_k \leq r2_k \leq N
  • 1 \leq c1_k \leq c2_k \leq M
  • 入力はすべて整数である

入力

N M Q
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}
r1_1 c1_1 r2_1 c2_1
r1_2 c1_2 r2_2 c2_2
\vdots
r1_Q c1_Q r2_Q c2_Q
  • 1 行目には、グリッドの行数を表す整数 N 、列数を表す整数 M 、操作の回数を表す整数 Q が、スペース区切りで与えられる。
  • 続く N 行で、照明の初期の明るさが与えられる。
  • このうち i 行目 (1 \leq i \leq N) では、グリッドの i 行目の各列の明るさ B_{i,1}, B_{i,2}, \ldots, B_{i,M} がスペース区切りで与えられる。
  • 続く Q 行で、各操作の長方形領域が与えられる。
  • このうち k 行目 (1 \leq k \leq Q) では、k 回目の操作における長方形領域の左上の行番号 r1_k 、左上の列番号 c1_k 、右下の行番号 r2_k 、右下の列番号 c2_k がスペース区切りで与えられる。

出力

すべての操作が終わった後の、会場全体の照明の明るさの合計を整数として 1 行で出力せよ。


入力例 1

2 3 1
1 2 3
4 5 6
1 1 2 2

出力例 1

33

入力例 2

2 2 2
5 3
2 4
1 1 2 2
1 1 2 2

出力例 2

14

入力例 3

4 4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 2 3
2 2 4 4
1 1 4 4

出力例 3

175

入力例 4

5 6 5
10 20 30 40 50 60
15 25 35 45 55 65
12 22 32 42 52 62
18 28 38 48 58 68
11 21 31 41 51 61
1 1 3 4
2 3 5 6
1 1 5 6
3 2 4 5
1 5 2 6

出力例 4

1614

入力例 5

1 1 1
7
1 1 1 1

出力例 5

14

Score : 400 pts

Problem Statement

Takahashi has installed lights in an N-row by M-column grid at an event venue. Each light has an initial brightness setting, and the initial brightness of the light at row i, column j is B_{i,j}.

As part of the event's production, Takahashi decided to adjust the brightness of the lights. Each light has a switch, and each time the switch is pressed, the light toggles between "normal mode" and "enhanced mode." Initially, all lights are in normal mode.

Takahashi performs Q switch operations in order. In the k-th operation (1 \leq k \leq Q), he presses the switch once for every light within the rectangular region specified by the input, namely the region with top-left corner (r1_k, c1_k) and bottom-right corner (r2_k, c2_k). Here, light (i, j) is contained in this rectangular region if and only if r1_k \leq i \leq r2_k and c1_k \leq j \leq c2_k.

After all Q operations are completed, the final brightness of each light is determined by its mode as follows:

  • Enhanced mode lights (switch pressed an odd number of times): brightness is 2 \times B_{i,j}
  • Normal mode lights (switch pressed an even number of times; 0 counts as even): brightness is B_{i,j}

Find the total brightness of all lights in the venue after all operations are completed.

Constraints

  • 1 \leq N \leq 1500
  • 1 \leq M \leq 1500
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq B_{i,j} \leq 10^4
  • 1 \leq r1_k \leq r2_k \leq N
  • 1 \leq c1_k \leq c2_k \leq M
  • All input values are integers

Input

N M Q
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}
r1_1 c1_1 r2_1 c2_1
r1_2 c1_2 r2_2 c2_2
\vdots
r1_Q c1_Q r2_Q c2_Q
  • The first line contains three space-separated integers: N representing the number of rows in the grid, M representing the number of columns, and Q representing the number of operations.
  • The following N lines give the initial brightness of the lights.
  • The i-th of these lines (1 \leq i \leq N) contains the brightness values B_{i,1}, B_{i,2}, \ldots, B_{i,M} of each column in row i of the grid, separated by spaces.
  • The following Q lines give the rectangular region for each operation.
  • The k-th of these lines (1 \leq k \leq Q) contains four space-separated values: the top-left row number r1_k, the top-left column number c1_k, the bottom-right row number r2_k, and the bottom-right column number c2_k for the k-th operation.

Output

Output the total brightness of all lights in the venue after all operations are completed, as a single integer on one line.


Sample Input 1

2 3 1
1 2 3
4 5 6
1 1 2 2

Sample Output 1

33

Sample Input 2

2 2 2
5 3
2 4
1 1 2 2
1 1 2 2

Sample Output 2

14

Sample Input 3

4 4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 2 3
2 2 4 4
1 1 4 4

Sample Output 3

175

Sample Input 4

5 6 5
10 20 30 40 50 60
15 25 35 45 55 65
12 22 32 42 52 62
18 28 38 48 58 68
11 21 31 41 51 61
1 1 3 4
2 3 5 6
1 1 5 6
3 2 4 5
1 5 2 6

Sample Output 4

1614

Sample Input 5

1 1 1
7
1 1 1 1

Sample Output 5

14
E - 配達員の巡回

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

配点 : 433 点

問題文

ある街には N 個の地点があり、1 から N まで番号が付けられています。地点間を結ぶ M 本の双方向の道があり、i 番目の道は地点 A_i と地点 B_i を結び、通過するのに C_i の時間がかかります。同じ 2 地点間に複数の道が存在することもあります。

高橋君はこの街で働く配達員です。毎日、配送センターである地点 1 を出発し、いくつかの届け先を回って地点 1 に戻ってきます。

今日は K 個の届け先 V_1, V_2, \ldots, V_K が指定されています(届け先に地点 1 は含まれません)。高橋君は地点 1 を出発し、K 個の届け先すべてに少なくとも 1 回ずつ訪れてから、地点 1 に戻らなければなりません。移動の途中で同じ地点や同じ道を何度通ってもよいですが、道を通過するたびにその道の所要時間が加算されます。

このような経路における所要時間の合計の最小値を求めてください。

制約

  • 2 \leq N \leq 5 \times 10^4
  • 1 \leq M \leq 5 \times 10^4
  • 1 \leq K \leq 15
  • 2 \leq V_i \leq N (1 \leq i \leq K)
  • V_i はすべて異なる
  • 1 \leq A_i, B_i \leq N, A_i \neq B_i (1 \leq i \leq M)
  • 同じ 2 地点間に複数の道が存在することがある
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • すべての届け先は地点 1 から到達可能である
  • 入力はすべて整数である

入力

N M K
V_1 V_2 \ldots V_K
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M
  • 1 行目には、地点の数 N、道の数 M、届け先の数 K がスペース区切りで与えられる。
  • 2 行目には、K 個の届け先の番号 V_1, V_2, \ldots, V_K がスペース区切りで与えられる。
  • 続く M 行のうち i 行目 (1 \leq i \leq M) には、i 番目の道が結ぶ 2 つの地点 A_i, B_i と、その道の所要時間 C_i がスペース区切りで与えられる。

出力

地点 1 を出発し、K 個の届け先すべてに少なくとも 1 回ずつ訪れ、地点 1 に戻る経路について、所要時間の合計の最小値を 1 行で出力せよ。


入力例 1

4 5 2
2 3
1 2 2
2 3 3
3 1 4
1 4 10
4 3 1

出力例 1

9

入力例 2

5 8 2
3 5
1 2 1
2 3 1
1 3 10
1 3 3
1 4 2
4 5 2
3 5 100
2 5 5

出力例 2

12

入力例 3

8 12 3
4 6 8
1 2 2
2 3 2
3 4 2
1 5 3
5 6 3
6 7 3
7 8 3
4 8 4
2 5 2
3 6 2
4 7 2
1 8 20

出力例 3

22

入力例 4

14 22 5
4 7 9 12 14
1 2 4
2 3 3
3 4 5
4 5 2
5 6 4
6 7 3
7 8 6
8 9 2
9 10 4
10 11 3
11 12 5
12 13 2
13 14 4
1 5 7
2 6 6
4 8 5
5 9 8
7 11 4
9 13 3
3 10 12
6 12 9
1 14 30

出力例 4

51

入力例 5

16 15 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 1
1 3 2
1 4 3
1 5 4
1 6 5
1 7 6
1 8 7
1 9 8
1 10 9
1 11 10
1 12 11
1 13 12
1 14 13
1 15 14
1 16 1000000000

出力例 5

2000000210

Score : 433 pts

Problem Statement

A city has N locations, numbered from 1 to N. There are M bidirectional roads connecting locations, where the i-th road connects location A_i and location B_i and takes C_i time to traverse. There may be multiple roads between the same pair of locations.

Takahashi is a delivery person working in this city. Every day, he departs from location 1, which is the distribution center, visits several delivery destinations, and returns to location 1.

Today, K delivery destinations V_1, V_2, \ldots, V_K have been specified (location 1 is not included among the destinations). Takahashi must depart from location 1, visit all K destinations at least once each, and then return to location 1. During his travel, he may pass through the same location or the same road any number of times, but each time he traverses a road, its travel time is added to the total.

Find the minimum total travel time of such a route.

Constraints

  • 2 \leq N \leq 5 \times 10^4
  • 1 \leq M \leq 5 \times 10^4
  • 1 \leq K \leq 15
  • 2 \leq V_i \leq N (1 \leq i \leq K)
  • All V_i are distinct
  • 1 \leq A_i, B_i \leq N, A_i \neq B_i (1 \leq i \leq M)
  • There may be multiple roads between the same pair of locations
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • All destinations are reachable from location 1
  • All input values are integers

Input

N M K
V_1 V_2 \ldots V_K
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M
  • The first line contains the number of locations N, the number of roads M, and the number of destinations K, separated by spaces.
  • The second line contains the K destination numbers V_1, V_2, \ldots, V_K, separated by spaces.
  • The following M lines each contain, for the i-th line (1 \leq i \leq M), the two locations A_i, B_i connected by the i-th road and the travel time C_i of that road, separated by spaces.

Output

Print in one line the minimum total travel time of a route that departs from location 1, visits all K destinations at least once each, and returns to location 1.


Sample Input 1

4 5 2
2 3
1 2 2
2 3 3
3 1 4
1 4 10
4 3 1

Sample Output 1

9

Sample Input 2

5 8 2
3 5
1 2 1
2 3 1
1 3 10
1 3 3
1 4 2
4 5 2
3 5 100
2 5 5

Sample Output 2

12

Sample Input 3

8 12 3
4 6 8
1 2 2
2 3 2
3 4 2
1 5 3
5 6 3
6 7 3
7 8 3
4 8 4
2 5 2
3 6 2
4 7 2
1 8 20

Sample Output 3

22

Sample Input 4

14 22 5
4 7 9 12 14
1 2 4
2 3 3
3 4 5
4 5 2
5 6 4
6 7 3
7 8 6
8 9 2
9 10 4
10 11 3
11 12 5
12 13 2
13 14 4
1 5 7
2 6 6
4 8 5
5 9 8
7 11 4
9 13 3
3 10 12
6 12 9
1 14 30

Sample Output 4

51

Sample Input 5

16 15 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 1
1 3 2
1 4 3
1 5 4
1 6 5
1 7 6
1 8 7
1 9 8
1 10 9
1 11 10
1 12 11
1 13 12
1 14 13
1 15 14
1 16 1000000000

Sample Output 5

2000000210