D - City Tour Rally Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は N 個の都市を巡るラリーに参加します。都市にはそれぞれ 1 から N の番号が付けられています。

このラリーは 1 日目から K 日目までの K 日間にわたって行われます。高橋君は毎日ちょうど 1 つの都市に滞在します。1 日目には N 個の都市のうち好きな都市を選んで滞在できます。2 日目以降は、前日に滞在していた都市から移動ルートを使って別の都市へ移動し、そこに滞在します。

都市間の移動に使えるルートは M 本あり、いずれも一方通行です。k 番目のルートは都市 a_k から都市 b_k への移動を表し、このルートを使うと都市 a_k に滞在している日の翌日に都市 b_k に滞在できます（逆方向に移動できるとは限りません）。各ルートについて a_k \neq b_k が保証されます。

2 日目以降は、前日の滞在都市から出発する移動ルートが存在する都市にのみ移動できます。同じ都市への自己ループは存在しないため、連続する 2 日間に同じ都市に滞在することはできません。ただし、間に別の都市を挟んで同じ都市に再び滞在することは許されます。

各都市 i にはスコア基礎値 P_i が設定されています。j 日目（1 \leq j \leq K）に都市 i に滞在した場合に得られるスコアは (P_i \times j) \bmod Q です。ここで Q は与えられる正の整数であり、\bmod は非負の剰余を表します。

K 日間の滞在計画とは、長さ K の都市番号の列 c_1, c_2, \ldots, c_K であって、以下の条件をすべて満たすものを指します。

  • 各 c_j（1 \leq j \leq K）は 1 以上 N 以下の整数である（同じ都市番号が列中に複数回現れてもよい）。
  • すべての 1 \leq j \leq K - 1 に対して、都市 c_j から都市 c_{j+1} への移動ルートが存在する。

K 日間のスコアの合計、すなわち

\sum_{j=1}^{K} \bigl((P_{c_j} \times j) \bmod Q\bigr)

を最大化してください。すべての有効な滞在計画に対するこの値の最大値を求めてください。

なお、有効な滞在計画が少なくとも 1 つ存在することが保証されます。

制約

  • 1 \leq N \leq 1000
  • 0 \leq M \leq \min(N \times (N - 1),\; 50000)
  • 1 \leq K \leq 1000
  • 1 \leq Q \leq 10^6
  • 0 \leq P_i \leq 10^6（1 \leq i \leq N）
  • 1 \leq a_k, b_k \leq N（1 \leq k \leq M）
  • a_k \neq b_k（1 \leq k \leq M）
  • 移動ルートに重複はない（すなわち、(a_k, b_k) はすべて相異なる）
  • 有効な滞在計画が少なくとも 1 つ存在する
  • 入力はすべて整数である

入力

N M K Q
P_1 P_2 \ldots P_N
a_1 b_1
a_2 b_2
\vdots
a_M b_M
  • 1 行目には、都市の数 N、移動ルートの数 M、ラリーの日数 K、スコア計算に用いる正の整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各都市のスコア基礎値 P_1, P_2, \ldots, P_N がスペース区切りで与えられる。
  • 続く M 行のうち k 行目（1 \leq k \leq M）には a_k と b_k がスペース区切りで与えられ、都市 a_k から都市 b_k への一方通行の移動ルートが存在することを表す。M = 0 の場合、この部分は存在しない。

出力

K 日間のスコアの合計の最大値を 1 行で出力せよ。

入力例 1

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

出力例 1

24

入力例 2

4 5 3 13
4 9 1 7
1 2
1 3
2 4
3 4
4 1

出力例 2

22

入力例 3

8 14 10 97
3 14 159 26 535 897 932 38
1 2
1 3
2 4
3 4
4 5
5 6
6 4
5 7
7 8
8 5
2 6
3 7
6 8
8 1

出力例 3

606

入力例 4

15 35 25 1000000
0 999999 123456 789012 345678 901234 567890 234567 890123 456789 111111 222222 333333 444444 555555
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 1
1 5
1 8
2 6
2 9
3 1
3 7
4 8
4 12
5 9
5 13
6 10
6 14
7 11
7 15
8 12
8 1
9 13
9 2
10 14
10 3

出力例 4

20223100

入力例 5

1 0 1 1
0

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi is participating in a rally that goes through N cities. The cities are numbered 1 through N.

This rally takes place over K days, from Day 1 to Day K. Takahashi stays in exactly one city each day. On Day 1, he can choose and stay in any of the N cities. From Day 2 onwards, he moves from the city he stayed in on the previous day to another city using a travel route, and stays there.

There are M travel routes available between cities, all of which are one-way. The k-th route represents travel from city a_k to city b_k. Using this route allows him to stay in city b_k on the day after he stayed in city a_k (travel in the reverse direction is not necessarily possible). It is guaranteed that a_k \neq b_k for each route.

From Day 2 onwards, he can only move to a city if there is a travel route starting from the city he stayed in on the previous day. Since there are no self-loops to the same city, he cannot stay in the same city for two consecutive days. However, he is allowed to stay in the same city again with other cities in between.

Each city i has a base score P_i. The score obtained by staying in city i on Day j (1 \leq j \leq K) is (P_i \times j) \bmod Q. Here, Q is a given positive integer, and \bmod denotes the non-negative remainder.

A staying plan for the K days is a sequence of city numbers of length K, c_1, c_2, \ldots, c_K, that satisfies all of the following conditions:

  • Each c_j (1 \leq j \leq K) is an integer between 1 and N, inclusive (the same city number may appear multiple times in the sequence).
  • For all 1 \leq j \leq K - 1, there exists a travel route from city c_j to city c_{j+1}.

Please maximize the total score over the K days, which is:

\sum_{j=1}^{K} \bigl((P_{c_j} \times j) \bmod Q\bigr)

Find the maximum value of this sum over all valid staying plans.

It is guaranteed that at least one valid staying plan exists.

Constraints

  • 1 \leq N \leq 1000
  • 0 \leq M \leq \min(N \times (N - 1),\; 50000)
  • 1 \leq K \leq 1000
  • 1 \leq Q \leq 10^6
  • 0 \leq P_i \leq 10^6 (1 \leq i \leq N)
  • 1 \leq a_k, b_k \leq N (1 \leq k \leq M)
  • a_k \neq b_k (1 \leq k \leq M)
  • There are no duplicate travel routes (i.e., all (a_k, b_k) are distinct).
  • There is at least one valid staying plan.
  • All input values are integers.

Input

N M K Q
P_1 P_2 \ldots P_N
a_1 b_1
a_2 b_2
\vdots
a_M b_M
  • The first line contains the number of cities N, the number of travel routes M, the number of days of the rally K, and the positive integer Q used for score calculation, separated by spaces.
  • The second line contains the base scores of the cities P_1, P_2, \ldots, P_N, separated by spaces.
  • The k-th of the following M lines (1 \leq k \leq M) contains a_k and b_k separated by a space, representing that there is a one-way travel route from city a_k to city b_k. If M = 0, this section is empty.

Output

Print the maximum total score over the K days in a single line.

Sample Input 1

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

Sample Output 1

24

Sample Input 2

4 5 3 13
4 9 1 7
1 2
1 3
2 4
3 4
4 1

Sample Output 2

22

Sample Input 3

8 14 10 97
3 14 159 26 535 897 932 38
1 2
1 3
2 4
3 4
4 5
5 6
6 4
5 7
7 8
8 5
2 6
3 7
6 8
8 1

Sample Output 3

606

Sample Input 4

15 35 25 1000000
0 999999 123456 789012 345678 901234 567890 234567 890123 456789 111111 222222 333333 444444 555555
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 1
1 5
1 8
2 6
2 9
3 1
3 7
4 8
4 12
5 9
5 13
6 10
6 14
7 11
7 15
8 12
8 1
9 13
9 2
10 14
10 3

Sample Output 4

20223100

Sample Input 5

1 0 1 1
0

Sample Output 5

0