問題文

この問題の回答は今年の B 問題の入力をひとつ作るために利用されます。B 問題も併せてお読みください。

下記の制約を満たす V 個の頂点と E 本の辺からなる無向グラフ 1 つと各頂点の座標を出力してください。

なお、グラフが連結である必要はありません。

ただし、 Text (cat) で提出してください。

制約

• 1 \leq V \leq 1000
• 0 \leq E \leq V \times (V-1) / 2
• 1 \leq a_i, b_i \leq V
• 0 \leq x_i, y_i \leq 10000
• a_i \neq b_i
• i \neq j ならば x_i \neq x_j または y_i \neq y_j
• i 番目の頂点は座標 (x_i,\ y_i) に位置する点であるものとする
• j 番目の辺は頂点 a_j と頂点 b_j を端点とする線分であるものとする
• 辺は他の辺と端点同士以外で接したり交差したり重なったりしない
• V, E, a_i, b_i, x_i, y_i は整数である

問題文

今年の A 問題の制約を満たすグラフが与えられます。

このグラフを隣接する頂点が同じ色にならないように 4 色で彩色してください。

制約

• 今年の A 問題を参照
• ただし、コンテスト開催時間中は、 1 \leq V \leq 10 の入力に対して正答すると AC となる

入力例 1

4 4
1 2
2 3
3 4
4 1

出力例 1

1
2
3
4

入力例 2

5 3
1 2
2 3
3 4

出力例 2

1
2
3
4
1

問題文

文字列 S と、要素数 M の単語の集合 P=\{P_1,\ P_2,\ …,\ P_M\} が与えられます。単語 P_i は、整数の重み W_i を持っています。

文字列 S から、P に含まれる単語を重なり合わないように取り出すことを考えます。単語の重みの総和が最大値をとるように取り出すとき、その最大値はいくつでしょうか？

なお、同じ単語を複数回取り出した場合、それらの単語は別々に数えることとします。

制約

• 1 \leq |S| \leq 200000
• 1 \leq M \leq 5000
• 1 \leq |P_i| \leq 200
• 1 \leq W_i \leq 10000
• S, P_i は英小文字からなる文字列である

入力例 1

abcabcabc
3
ab
bc
ca
1
1
1

出力例 1

4

入力例 2

abracadabra
4
b
abra
cad
rac
1
10
50
100

出力例 2

111

入力例 3

abcd
2
ad
bc
1192
794

出力例 3

794

問題文

ハシモトくんは、 N 個のタスクを割り当てられています。

タスク i は、一つ目のオフィスで作業する場合は A_i の時間が、二つ目のオフィスで作業する場合は B_i の時間がかかります。

n 回目のオフィス間の移動には C \times (n - 1) + D の時間がかかります。

また、タスク間には依存関係が M 個あり、タスク X_i を終わらせた後でないとタスク Y_i に着手できません。

ハシモトくんが最適に行動し、全てのタスクを終わらせるまでの時間を最小化した場合、かかる時間はどの程度になるでしょうか？

なお、タスク処理開始・終了はどちらのオフィスであっても良いものとします。

制約

• 1 \leq N \leq 20
• 0 \leq M \leq N \times (N-1) / 2
• 0 \leq C \leq 1000
• 0 \leq D \leq 1000
• 0 \leq A_i, B_i \leq 1000
• 1 \leq X_i, Y_i \leq N
• i \neq j ならば X_i \neq X_j または Y_i \neq Y_j
• タスク間の依存関係に循環はない
• N, M, C, D, A_i, B_i, X_i, Y_i は整数である

入力例 1

3 2 1 1
1 10
10 1
1 10
1 2
2 3

出力例 1

6

入力例 2

3 0 1 1
1 10
10 1
1 10

出力例 2

4

入力例 3

3 2 100 100
1 10
10 1
1 10
3 2
2 1

出力例 3

12

入力例 4

4 4 3 8
100 1
1 100
1 100
100 1
1 2
1 3
2 4
3 4

出力例 4

23