E - 都市巡りとミッション達成 解説 /

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

配点 : 433 点

問題文

高橋君は 1 から N までの番号がついた N 個の都市がある国を旅行しています。高橋君は最初、都市 1 にいます。都市 1 は最初から訪問済みです。

都市間には M 本の一方通行の道路があり、 i 番目の道路を使うと都市 U_i から都市 V_i へ W_i 時間かけて移動できます。同じ2都市間に複数の道路が存在することもあります。高橋君は同じ都市や同じ道路を何度通っても構いません。

高橋君は都市 1 から出発し、道路を辿って移動します（一度も移動しなくてもよいです）。ただし、通った道路の移動時間の総和は T 以下でなければなりません。最終的にどの都市にいるかは問いません。一度でも到達した都市は訪問済みとして扱います（都市 1 も訪問済みに含まれます）。

この国では K 個のミッションが設定されています。 j 番目のミッションは都市の集合 S_j と報酬 P_j の組で表され、「S_j に含まれるすべての都市が訪問済みであれば、報酬 P_j を獲得できる」というものです。訪問の順序は問いません。条件を満たすミッションはすべて同時に達成でき、獲得する報酬はそれらの合計となります。

高橋君が獲得できる報酬の合計の最大値を求めてください。どのミッションの条件も満たせない場合、答えは 0 です。

制約

  • 2 \leq N \leq 10^4
  • 1 \leq M \leq 10^4
  • 1 \leq K \leq 100
  • 1 \leq T \leq 10^9
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^6
  • 1 \leq |S_j| \leq 14
  • S_j の各要素 s_{j,k} は 1 \leq s_{j,k} \leq N を満たす
  • 各 S_j の要素はすべて相異なる
  • 異なるミッション間で S_j が同一の集合であることもありうる
  • \bigcup_{j=1}^{K} S_j の要素数は 14 以下である（すなわち、すべてのミッションに登場する都市の種類数は高々 14）
  • 1 \leq P_j \leq 10^9
  • 入力はすべて整数である

入力

N M K T
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
|S_1| s_{1,1} s_{1,2} \ldots s_{1,|S_1|} P_1
|S_2| s_{2,1} s_{2,2} \ldots s_{2,|S_2|} P_2
\vdots
|S_K| s_{K,1} s_{K,2} \ldots s_{K,|S_K|} P_K
  • 1 行目には、都市の数 N 、道路の数 M 、ミッションの数 K 、移動可能な合計時間 T がスペース区切りで与えられる。
  • 続く M 行のうち i 行目では、 i 番目の道路の始点 U_i 、終点 V_i 、移動時間 W_i がスペース区切りで与えられる。
  • 続く K 行のうち j 行目では、 j 番目のミッションが与えられる。まず集合 S_j の要素数 |S_j| が与えられ、続いて S_j に含まれる都市の番号 s_{j,1}, s_{j,2}, \ldots, s_{j,|S_j|} が与えられ、最後に報酬 P_j が与えられる。これらはすべてスペース区切りである。

出力

高橋君が獲得できる報酬の合計の最大値を 1 行で出力せよ。どのミッションの条件も満たせない場合は 0 を出力せよ。

入力例 1

4 4 3 7
1 2 3
2 3 3
1 4 10
3 4 1
1 2 100
2 2 3 300
1 4 500

出力例 1

900

入力例 2

3 1 2 5
1 2 10
1 2 100
1 3 200

出力例 2

0

入力例 3

12 18 8 25
1 2 4
1 3 6
2 4 5
3 4 2
4 5 4
2 6 10
5 6 3
6 7 2
7 8 4
3 9 8
9 10 3
10 5 2
8 11 5
11 12 1
5 3 7
6 2 6
4 10 6
10 8 4
1 2 100
2 3 4 250
3 2 5 6 500
2 8 10 700
1 11 900
4 2 4 6 8 1200
2 10 5 400
3 3 9 10 350

出力例 3

1850

入力例 4

30 50 15 120
1 2 5
1 3 12
1 4 7
2 5 8
2 6 20
3 6 6
4 3 3
4 7 15
5 8 10
6 8 5
6 9 9
7 10 8
8 11 4
9 11 3
10 12 6
11 12 5
12 13 7
13 14 2
14 15 5
15 16 8
16 18 6
13 18 15
18 20 9
20 22 10
22 25 12
25 30 14
12 20 25
8 15 18
5 10 22
3 5 20
2 3 4
11 7 11
15 8 16
18 12 13
20 15 7
22 18 5
25 22 9
30 1 50
9 17 10
17 19 7
19 21 4
21 23 6
23 24 3
24 26 8
26 27 4
27 28 5
28 29 3
29 30 2
10 20 30
6 18 40
1 1 100
1 2 150
2 2 5 400
3 3 8 12 900
2 15 18 1200
4 2 7 10 12 1300
3 20 22 25 2000
1 30 3000
5 1 3 5 8 15 1700
2 18 20 800
3 10 12 20 1100
4 15 20 22 25 1600
2 25 30 2200
6 2 3 5 7 8 10 2500
3 12 18 30 1800

出力例 4

14350

入力例 5

2 1 1 1
2 1 1000000
1 1 1000000000

出力例 5

1000000000

Score : 433 pts

Problem Statement

Takahashi is traveling in a country with N cities numbered from 1 to N. Takahashi is initially in city 1. City 1 is already considered visited from the start.

There are M one-way roads between cities. Using the i-th road, one can travel from city U_i to city V_i in W_i units of time. There may be multiple roads between the same pair of cities. Takahashi may pass through the same city or the same road any number of times.

Takahashi starts from city 1 and travels along roads (he may also choose not to move at all). However, the total travel time of all roads taken must not exceed T. It does not matter which city he ends up in. Any city that has been reached at least once is treated as visited (city 1 is also included as visited).

In this country, K missions are available. The j-th mission is represented by a pair of a set of cities S_j and a reward P_j, meaning "if all cities in S_j have been visited, reward P_j can be obtained." The order of visits does not matter. All missions whose conditions are satisfied can be completed simultaneously, and the total reward earned is the sum of their individual rewards.

Find the maximum total reward that Takahashi can earn. If no mission's condition can be satisfied, the answer is 0.

Constraints

  • 2 \leq N \leq 10^4
  • 1 \leq M \leq 10^4
  • 1 \leq K \leq 100
  • 1 \leq T \leq 10^9
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^6
  • 1 \leq |S_j| \leq 14
  • Each element s_{j,k} of S_j satisfies 1 \leq s_{j,k} \leq N
  • All elements within each S_j are distinct
  • Different missions may have the same set S_j
  • The number of elements in \bigcup_{j=1}^{K} S_j is at most 14 (that is, the total number of distinct cities appearing across all missions is at most 14)
  • 1 \leq P_j \leq 10^9
  • All input values are integers

Input

N M K T
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
|S_1| s_{1,1} s_{1,2} \ldots s_{1,|S_1|} P_1
|S_2| s_{2,1} s_{2,2} \ldots s_{2,|S_2|} P_2
\vdots
|S_K| s_{K,1} s_{K,2} \ldots s_{K,|S_K|} P_K
  • The first line contains the number of cities N, the number of roads M, the number of missions K, and the maximum total travel time T, separated by spaces.
  • In the following M lines, the i-th line gives the starting city U_i, the ending city V_i, and the travel time W_i of the i-th road, separated by spaces.
  • In the following K lines, the j-th line gives the j-th mission. First, the number of elements |S_j| in set S_j is given, followed by the city numbers s_{j,1}, s_{j,2}, \ldots, s_{j,|S_j|} contained in S_j, and finally the reward P_j. All values are separated by spaces.

Output

Output in one line the maximum total reward that Takahashi can earn. If no mission's condition can be satisfied, output 0.

Sample Input 1

4 4 3 7
1 2 3
2 3 3
1 4 10
3 4 1
1 2 100
2 2 3 300
1 4 500

Sample Output 1

900

Sample Input 2

3 1 2 5
1 2 10
1 2 100
1 3 200

Sample Output 2

0

Sample Input 3

12 18 8 25
1 2 4
1 3 6
2 4 5
3 4 2
4 5 4
2 6 10
5 6 3
6 7 2
7 8 4
3 9 8
9 10 3
10 5 2
8 11 5
11 12 1
5 3 7
6 2 6
4 10 6
10 8 4
1 2 100
2 3 4 250
3 2 5 6 500
2 8 10 700
1 11 900
4 2 4 6 8 1200
2 10 5 400
3 3 9 10 350

Sample Output 3

1850

Sample Input 4

30 50 15 120
1 2 5
1 3 12
1 4 7
2 5 8
2 6 20
3 6 6
4 3 3
4 7 15
5 8 10
6 8 5
6 9 9
7 10 8
8 11 4
9 11 3
10 12 6
11 12 5
12 13 7
13 14 2
14 15 5
15 16 8
16 18 6
13 18 15
18 20 9
20 22 10
22 25 12
25 30 14
12 20 25
8 15 18
5 10 22
3 5 20
2 3 4
11 7 11
15 8 16
18 12 13
20 15 7
22 18 5
25 22 9
30 1 50
9 17 10
17 19 7
19 21 4
21 23 6
23 24 3
24 26 8
26 27 4
27 28 5
28 29 3
29 30 2
10 20 30
6 18 40
1 1 100
1 2 150
2 2 5 400
3 3 8 12 900
2 15 18 1200
4 2 7 10 12 1300
3 20 22 25 2000
1 30 3000
5 1 3 5 8 15 1700
2 18 20 800
3 10 12 20 1100
4 15 20 22 25 1600
2 25 30 2200
6 2 3 5 7 8 10 2500
3 12 18 30 1800

Sample Output 4

14350

Sample Input 5

2 1 1 1
2 1 1000000
1 1 1000000000

Sample Output 5

1000000000