Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
H 行 W 列のマス目を考えます。上から r 番目、左から c 番目のマスを (r, c) と表すことにします。 全てのマスはそれぞれ白か黒のどちらかの色に塗られています。
次のような経路が存在するとき、このマス目を"良い"状態と呼びます。
- 常に白いマスの上にいながら、(1, 1) から、一つ 右か下 のマスに移動することを繰り返し、 (H, W) へ移動する。
ここで、"良い"状態ならば (1, 1) や (H, W) が必ず白いことに注意してください。
あなたの仕事は、以下の操作を繰り返し、マス目を"良い"状態にすることです。最小で何回操作を行う必要があるか求めてください。なお、有限回の操作で必ず"良い"状態に出来ることが証明可能です。
- 4 つの整数 r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W) を選ぶ。r_0 \leq r \leq r_1, c_0 \leq c \leq c_1 を満たす全ての r, c について、(r, c) の色を変更する。つまり、白色ならば黒色にし、黒色ならば白色にする。
制約
- 2 \leq H, W \leq 100
入力
入力は以下の形式で標準入力から与えられる。
H W s_{11} s_{12} \cdots s_{1W} s_{21} s_{22} \cdots s_{2W} \vdots s_{H1} s_{H2} \cdots s_{HW}
ここで、s_{rc} は #
か .
であり、#
は (r, c) が黒色、.
は白色であることを表す。
出力
最小の操作回数を出力せよ。
入力例 1
3 3 .## .#. ##.
出力例 1
1
(r_0, c_0, r_1, c_1) = (2, 2, 2, 2)、つまりマス (2, 2) のみ色を変更すれば良いです。
入力例 2
2 2 #. .#
出力例 2
2
入力例 3
4 4 ..## #... ###. ###.
出力例 3
0
操作が必要ない場合も存在します。
入力例 4
5 5 .#.#. #.#.# .#.#. #.#.# .#.#.
出力例 4
4
Score : 400 points
Problem Statement
Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.
The grid is said to be good if and only if the following condition is satisfied:
- From (1, 1), we can reach (H, W) by moving one square right or down repeatedly, while always being on a white square.
Note that (1, 1) and (H, W) must be white if the grid is good.
Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.
- Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) - that is, from white to black and vice versa.
Constraints
- 2 \leq H, W \leq 100
Input
Input is given from Standard Input in the following format:
H W s_{11} s_{12} \cdots s_{1W} s_{21} s_{22} \cdots s_{2W} \vdots s_{H1} s_{H2} \cdots s_{HW}
Here s_{rc} represents the color of (r, c) - #
stands for black, and .
stands for white.
Output
Print the minimum number of operations needed.
Sample Input 1
3 3 .## .#. ##.
Sample Output 1
1
Do the operation with (r_0, c_0, r_1, c_1) = (2, 2, 2, 2) to change just the color of (2, 2), and we are done.
Sample Input 2
2 2 #. .#
Sample Output 2
2
Sample Input 3
4 4 ..## #... ###. ###.
Sample Output 3
0
No operation may be needed.
Sample Input 4
5 5 .#.#. #.#.# .#.#. #.#.# .#.#.
Sample Output 4
4
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
各要素が 1 か 2 か 3 である長さ N の数字列 a_1a_2\ldots a_N が与えられます。 x_{i,j} を次のように定義します。
- x_{1,j} := a_j \quad (1 \leq j \leq N)
- x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N かつ 1 \leq j \leq N+1-i)
x_{N,1} を求めてください。
制約
- 2 ≦ N ≦ 10^6
- a_i = 1,2,3 (1 \leq i \leq N)
入力
入力は以下の形式で標準入力から与えられる。
N a_1a_2\ldotsa_N
出力
x_{N,1} を出力せよ。
入力例 1
4 1231
出力例 1
1
x_{1,1},x_{1,2},x_{1,3},x_{1,4} はそれぞれ、1,2,3,1 です。
x_{2,1},x_{2,2},x_{2,3} はそれぞれ、|1-2| = 1,|2-3| = 1,|3-1| = 2 です。
x_{3,1},x_{3,2} はそれぞれ、|1-1| = 0,|1-2| = 1 です。
最後に、 x_{4,1} = |0-1| = 1 なので、答えは 1 です。
入力例 2
10 2311312312
出力例 2
0
Score : 700 points
Problem Statement
Given is a sequence of N digits a_1a_2\ldots a_N, where each element is 1, 2, or 3. Let x_{i,j} defined as follows:
- x_{1,j} := a_j \quad (1 \leq j \leq N)
- x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N and 1 \leq j \leq N+1-i)
Find x_{N,1}.
Constraints
- 2 \leq N \leq 10^6
- a_i = 1,2,3 (1 \leq i \leq N)
Input
Input is given from Standard Input in the following format:
N a_1a_2\ldotsa_N
Output
Print x_{N,1}.
Sample Input 1
4 1231
Sample Output 1
1
x_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1.
x_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2.
x_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1.
Finally, x_{4,1} = |0-1| = 1, so the answer is 1.
Sample Input 2
10 2311312312
Sample Output 2
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
N 頂点の、それぞれ M_1, M_2, M_3 辺の単純な無向グラフ X, Y, Z が与えられます。 頂点をそれぞれ x_1, x_2, \dots, x_N, y_1, y_2, \dots, y_N, z_1, z_2, \dots, z_N とします。 X, Y, Z の辺はそれぞれ (x_{a_i}, x_{b_i}), (y_{c_i}, y_{d_i}), (z_{e_i}, z_{f_i}) です。
X, Y, Z を元に N^3 頂点の無向グラフ W を作ります。 X, Y, Z から 1 つずつ頂点を選ぶ方法は N^3 通りありますが、これがそれぞれ W の頂点と一対一に対応します。x_i, y_j, z_k を選ぶことに対応する頂点を (x_i, y_j, z_k) で表すこととします。
W の辺を、以下の手順に沿って張ります。
- X の各辺 (x_u, x_v)、及び全ての w, l について、(x_u, y_w, z_l), (x_v, y_w, z_l) 間に辺を張る
- Y の各辺 (y_u, y_v)、及び全ての w, l について、(x_w, y_u, z_l), (x_w, y_v, z_l) 間に辺を張る
- Z の各辺 (z_u, z_v)、及び全ての w, l について、(x_w, y_l, z_u), (x_w, y_l, z_v) 間に辺を張る
そして、W の頂点 (x_i, y_j, z_k) の重みを 1,000,000,000,000,000,000^{(i +j + k)} = 10^{18(i + j + k)} とします。W の独立集合のうち、頂点の重みの総和の最大値を求めてください。そしてそれを 998,244,353 で割った余りを出力してください。
制約
- 2 \leq N \leq 100,000
- 1 \leq M_1, M_2, M_3 \leq 100,000
- 1 \leq a_i, b_i, c_i, d_i, e_i, f_i \leq N
- X, Y, Z は単純、つまり自己ループや多重辺は存在しない
入力
入力は以下の形式で標準入力から与えられる。
N M_1 a_1 b_1 a_2 b_2 \vdots a_{M_1} b_{M_1} M_2 c_1 d_1 c_2 d_2 \vdots c_{M_2} d_{M_2} M_3 e_1 f_1 e_2 f_2 \vdots e_{M_3} f_{M_3}
出力
重みの総和の最大値を 998,244,353 で割った余りを出力せよ。
入力例 1
2 1 1 2 1 1 2 1 1 2
出力例 1
46494701
(x_2, y_1, z_1), (x_1, y_2, z_1), (x_1, y_1, z_2), (x_2, y_2, z_2) を選ぶ場合が最適です。 答えは 3 \times 10^{72} + 10^{108} を 998,244,353 で割ったあまりの 46,494,701 です。
入力例 2
3 3 1 3 1 2 3 2 2 2 1 2 3 1 2 1
出力例 2
883188316
入力例 3
100000 1 1 2 1 99999 100000 1 1 100000
出力例 3
318525248
Score : 900 points
Problem Statement
Given are simple undirected graphs X, Y, Z, with N vertices each and M_1, M_2, M_3 edges, respectively. The vertices in X, Y, Z are respectively called x_1, x_2, \dots, x_N, y_1, y_2, \dots, y_N, z_1, z_2, \dots, z_N. The edges in X, Y, Z are respectively (x_{a_i}, x_{b_i}), (y_{c_i}, y_{d_i}), (z_{e_i}, z_{f_i}).
Based on X, Y, Z, we will build another undirected graph W with N^3 vertices. There are N^3 ways to choose a vertex from each of the graphs X, Y, Z. Each of these choices corresponds to the vertices in W one-to-one. Let (x_i, y_j, z_k) denote the vertex in W corresponding to the choice of x_i, y_j, z_k.
We will span edges in W as follows:
- For each edge (x_u, x_v) in X and each w, l, span an edge between (x_u, y_w, z_l) and (x_v, y_w, z_l).
- For each edge (y_u, y_v) in Y and each w, l, span an edge between (x_w, y_u, z_l) and (x_w, y_v, z_l).
- For each edge (z_u, z_v) in Z and each w, l, span an edge between (x_w, y_l, z_u) and (x_w, y_l, z_v).
Then, let the weight of the vertex (x_i, y_j, z_k) in W be 1,000,000,000,000,000,000^{(i +j + k)} = 10^{18(i + j + k)}. Find the maximum possible total weight of the vertices in an independent set in W, and print that total weight modulo 998,244,353.
Constraints
- 2 \leq N \leq 100,000
- 1 \leq M_1, M_2, M_3 \leq 100,000
- 1 \leq a_i, b_i, c_i, d_i, e_i, f_i \leq N
- X, Y, and Z are simple, that is, they have no self-loops and no multiple edges.
Input
Input is given from Standard Input in the following format:
N M_1 a_1 b_1 a_2 b_2 \vdots a_{M_1} b_{M_1} M_2 c_1 d_1 c_2 d_2 \vdots c_{M_2} d_{M_2} M_3 e_1 f_1 e_2 f_2 \vdots e_{M_3} f_{M_3}
Output
Print the maximum possible total weight of an independent set in W, modulo 998,244,353.
Sample Input 1
2 1 1 2 1 1 2 1 1 2
Sample Output 1
46494701
The maximum possible total weight of an independent set is that of the set (x_2, y_1, z_1), (x_1, y_2, z_1), (x_1, y_1, z_2), (x_2, y_2, z_2). The output should be (3 \times 10^{72} + 10^{108}) modulo 998,244,353, which is 46,494,701.
Sample Input 2
3 3 1 3 1 2 3 2 2 2 1 2 3 1 2 1
Sample Output 2
883188316
Sample Input 3
100000 1 1 2 1 99999 100000 1 1 100000
Sample Output 3
318525248
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
正整数 N が与えられます。 (1,2,\cdots,3N) の順列 (P_1,P_2,\cdots,P_{3N})であって、次の操作によって生成されうるものの数を求めてください。 ただし、答えは非常に大きくなることがあるので、素数 M で割ったあまりを求めてください。
- 長さ 3 の数列を N 個用意する。この数列たちを A_1,A_2,\cdots ,A_N とする。この 3N 個の値には 1 から 3N がちょうど一度ずつ登場せねばならない。
- 空の数列 P を用意する。以下の操作を 3N 回繰り返す。
- 各数列 A_i のうち、空でないものの先頭の要素を見て、そのうち最小の要素を x とする。
- x を A_i から消去する。 P の最後尾に x を追加する。
制約
- 1 \leq N \leq 2000
- 10^8 \leq M \leq 10^9+7
- M は素数
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
条件を満たす順列の数を M で割ったあまりを出力せよ。
入力例 1
1 998244353
出力例 1
6
すべての長さ 3 の順列が条件を満たします。
入力例 2
2 998244353
出力例 2
261
入力例 3
314 1000000007
出力例 3
182908545
Score : 1200 points
Problem Statement
Given is a positive integer N. Find the number of permutations (P_1,P_2,\cdots,P_{3N}) of (1,2,\cdots,3N) that can be generated through the procedure below. This number can be enormous, so print it modulo a prime number M.
- Make N sequences A_1,A_2,\cdots,A_N of length 3 each, using each of the integers 1 through 3N exactly once.
- Let P be an empty sequence, and do the following operation 3N times.
- Among the elements that are at the beginning of one of the sequences A_i that is non-empty, let the smallest be x.
- Remove x from the sequence, and add x at the end of P.
Constraints
- 1 \leq N \leq 2000
- 10^8 \leq M \leq 10^9+7
- M is a prime number.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the number of permutations modulo M.
Sample Input 1
1 998244353
Sample Output 1
6
All permutations of length 3 count.
Sample Input 2
2 998244353
Sample Output 2
261
Sample Input 3
314 1000000007
Sample Output 3
182908545
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1400 点
問題文
正整数 N と、長さ 2^N の 0 か 1 からなる数列 A_0,A_1,\ldots,A_{2^N-1} が与えられます。 2^N 個すべての S \subseteq \{0,1,\ldots,N-1 \} について、以下の条件を満たす閉曲線 C が存在するか判定し、存在する場合はひとつ構成してください。
- x = \sum_{i \in S} 2^i とする。また、点集合 B_S を \{ (i+0.5,0.5) | i \in S \} と定義する。
- 閉曲線 C を B_S を通らずに連続的に動かして、閉曲線上のすべての点の y 座標を負にするような方法が存在するならば、A_x = 1 である。
- 閉曲線 C を B_S を通らずに連続的に動かして、閉曲線上のすべての点の y 座標を負にするような方法が存在しないならば、A_x = 0 である。
出力方法に関しては、"出力" のチャプターを読んでください。
補足
C が閉曲線であるとは、次のように定義される。
- C は [0,1] から \mathbb{R}^2 への連続関数であり、C(0) = C(1) を満たす。
閉曲線 C を点集合 X を通らずに閉曲線 D に連続的に動かせるとは、次のように定義される。
- 次の条件を満たす関数 f : [0,1] \times [0,1] \rightarrow \mathbb{R}^2 が存在する。
- f は連続。
- f(0,t) = C(t)
- f(1,t) = D(t)
- f(x,t) \notin X
制約
- 1 \leq N \leq 8
- A_i = 0,1 \quad (0 \leq i \leq 2^N-1)
- A_0 = 1
入力
入力は以下の形式で標準入力から与えられる。
N A_0A_1 \cdots A_{2^N-1}
出力
条件を満たす閉曲線が存在しないならば Impossible
と出力せよ。
存在するならば、まず 1 行目に Possible
と出力せよ。
その後、以下の形式で構成した閉曲線を出力せよ。
L x_0 y_0 x_1 y_1 : x_L y_L
これは、閉曲線として (x_0,y_0),(x_1,y_1),\ldots,(x_L,y_L) をこの順に通る閉折れ線を選ぶことを意味する。
出力は次の条件を満たしている必要がある。
- 0 \leq x_i \leq N, 0 \leq y_i \leq 1, x_i,y_i は整数 \quad (0 \leq i \leq L)
- |x_i-x_{i+1}| + |y_i-y_{i+1}| = 1 \quad (0 \leq i \leq L-1)
- (x_0,y_0) = (x_L,y_L)
また、閉曲線の長さ L は、 0 \leq L \leq 250000 を満たす必要がある。
もとの問題で条件を満たす閉曲線が存在するならば、この出力形式のもとでも存在することが証明できる。
入力例 1
1 10
出力例 1
Possible 4 0 0 0 1 1 1 1 0 0 0
S = \emptyset のときは閉曲線上のすべての点の y 座標を負にすることが可能です。
S = \{0\} のときはどのようにしても閉曲線上のすべての点の y 座標を負にすることはできません。
入力例 2
2 1000
出力例 2
Possible 6 1 0 2 0 2 1 1 1 0 1 0 0 1 0
出力は図のような閉曲線を表しています。
入力例 3
2 1001
出力例 3
Impossible
入力例 4
1 11
出力例 4
Possible 0 1 1
Score : 1400 points
Problem Statement
Given are a positive integer N and a sequence of length 2^N consisting of 0s and 1s: A_0,A_1,\ldots,A_{2^N-1}. Determine whether there exists a closed curve C that satisfies the condition below for all 2^N sets S \subseteq \{0,1,\ldots,N-1 \}. If the answer is yes, construct one such closed curve.
- Let x = \sum_{i \in S} 2^i and B_S be the set of points \{ (i+0.5,0.5) | i \in S \}.
- If there is a way to continuously move the closed curve C without touching B_S so that every point on the closed curve has a negative y-coordinate, A_x = 1.
- If there is no such way, A_x = 0.
For instruction on printing a closed curve, see Output below.
Notes
C is said to be a closed curve if and only if:
- C is a continuous function from [0,1] to \mathbb{R}^2 such that C(0) = C(1).
We say that a closed curve C can be continuously moved without touching a set of points X so that it becomes a closed curve D if and only if:
- There exists a function f : [0,1] \times [0,1] \rightarrow \mathbb{R}^2 that satisfies all of the following.
- f is continuous.
- f(0,t) = C(t).
- f(1,t) = D(t).
- f(x,t) \notin X.
Constraints
- 1 \leq N \leq 8
- A_i = 0,1 \quad (0 \leq i \leq 2^N-1)
- A_0 = 1
Input
Input is given from Standard Input in the following format:
N A_0A_1 \cdots A_{2^N-1}
Output
If there is no closed curve that satisfies the condition, print Impossible
.
If such a closed curve exists, print Possible
in the first line.
Then, print one such curve in the following format:
L x_0 y_0 x_1 y_1 : x_L y_L
This represents the closed polyline that passes (x_0,y_0),(x_1,y_1),\ldots,(x_L,y_L) in this order.
Here, all of the following must be satisfied:
- 0 \leq x_i \leq N, 0 \leq y_i \leq 1, and x_i, y_i are integers. (0 \leq i \leq L)
- |x_i-x_{i+1}| + |y_i-y_{i+1}| = 1. (0 \leq i \leq L-1)
- (x_0,y_0) = (x_L,y_L).
Additionally, the length of the closed curve L must satisfy 0 \leq L \leq 250000.
It can be proved that, if there is a closed curve that satisfies the condition in Problem Statement, there is also a closed curve that can be expressed in this format.
Sample Input 1
1 10
Sample Output 1
Possible 4 0 0 0 1 1 1 1 0 0 0
When S = \emptyset, we can move this curve so that every point on it has a negative y-coordinate.
When S = \{0\}, we cannot do so.
Sample Input 2
2 1000
Sample Output 2
Possible 6 1 0 2 0 2 1 1 1 0 1 0 0 1 0
The output represents the following curve:
Sample Input 3
2 1001
Sample Output 3
Impossible
Sample Input 4
1 11
Sample Output 4
Possible 0 1 1
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 2100 点
問題文
1 から N までの番号のついた N 軒の宝石店があります.
宝石店 i (1 \leq i \leq N) では,K_i 種類の宝石が売られています. このうち,j (1 \leq j \leq K_i) 種類目の宝石は,大きさが S_{i,j},値段が P_{i,j} で,在庫が C_{i,j} 個あります.
よい 宝石箱とは,以下の条件をすべて満たす宝石箱です.
- 宝石箱の中には,各宝石店で買った宝石が 1 個ずつ入っている.
- 次の M 個の条件をすべて満たす.
- i (1 \leq i \leq M) 番目の条件: (宝石店 V_i で買った宝石の大きさ)\leq (宝石店 U_i で買った宝石の大きさ)+W_i
次の Q 個の質問に答えてください. i (1 \leq i \leq Q) 番目の質問では,整数 A_i が与えられるので,A_i 個のよい宝石箱を準備するとき,買う宝石の値段の合計の最小値を求めてください. ただし,A_i 個のよい宝石箱が準備できない場合はその旨を答えてください.
制約
- 1 \leq N \leq 30
- 1 \leq K_i \leq 30
- 1 \leq S_{i,j} \leq 10^9
- 1 \leq P_{i,j} \leq 30
- 1 \leq C_{i,j} \leq 10^{12}
- 0 \leq M \leq 50
- 1 \leq U_i,V_i \leq N
- U_i \neq V_i
- 0 \leq W_i \leq 10^9
- 1 \leq Q \leq 10^5
- 1 \leq A_i \leq 3 \times 10^{13}
- 入力は全て整数である.
入力
入力は以下の形式で標準入力から与えられる。
N 宝石店\ 1\ の情報 宝石店\ 2\ の情報 \vdots 宝石店\ N\ の情報 M U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M Q A_1 A_2 \vdots A_Q
宝石店 i (1 \leq i \leq N) の情報は,以下の形式で与えられる.
K_i S_{i,1} P_{i,1} C_{i,1} S_{i,2} P_{i,2} C_{i,2} \vdots S_{i,K_i} P_{i,K_i} C_{i,K_i}
出力
Q 行出力せよ. そのうち i 行目には,A_i 個のよい宝石箱を準備するときに買う宝石の値段の合計の最小値を出力せよ. ただし,A_i 個のよい宝石箱を準備することが不可能な場合は,-1 を出力せよ.
入力例 1
3 2 1 10 1 3 1 1 3 1 10 1 2 1 1 3 10 1 2 1 1 1 3 10 1 2 1 2 0 2 3 0 3 1 2 3
出力例 1
3 42 -1
宝石店 i で売られている j 種類目の宝石を宝石 (i,j) で表すことにします.
各クエリの答えは,以下のようになります.
- A_1=1: 宝石 (1,2),(2,2),(3,1) を使う宝石箱を準備すると,コストが 1+1+1=3 となり,最小.
- A_2=2: 宝石 (1,1),(2,1),(3,1) を使う宝石箱と,宝石 (1,2),(2,3),(3,2) を使う宝石箱を準備すると, コストが (10+10+1)+(1+10+10)=42 となり,最小.
- A_3=3: 3 つの良い宝石箱を準備することはできない.
入力例 2
5 5 86849520 30 272477201869 968023357 28 539131386006 478355090 8 194500792721 298572419 6 894877901270 203794105 25 594579473837 5 730211794 22 225797976416 842538552 9 420531931830 871332982 26 81253086754 553846923 29 89734736118 731788040 13 241088716205 5 903534485 22 140045153776 187101906 8 145639722124 513502442 9 227445343895 499446330 6 719254728400 564106748 20 333423097859 5 332809289 8 640911722470 969492694 21 937931959818 207959501 11 217019915462 726936503 12 382527525674 887971218 17 552919286358 5 444983655 13 487875689585 855863581 6 625608576077 885012925 10 105520979776 980933856 1 711474069172 653022356 19 977887412815 10 1 2 231274893 2 3 829836076 3 4 745221482 4 5 935448462 5 1 819308546 3 5 815839350 5 3 513188748 3 1 968283437 2 3 202352515 4 3 292999238 10 510266667947 252899314976 510266667948 374155726828 628866122125 628866122123 1 628866122124 510266667949 30000000000000
出力例 2
26533866733244 13150764378752 26533866733296 19456097795056 -1 33175436167096 52 33175436167152 26533866733352 -1
Score : 2100 points
Problem Statement
There are N jewelry shops numbered 1 to N.
Shop i (1 \leq i \leq N) sells K_i kinds of jewels. The j-th of these jewels (1 \leq j \leq K_i) has a size and price of S_{i,j} and P_{i,j}, respectively, and the shop has C_{i,j} jewels of this kind in stock.
A jewelry box is said to be good if it satisfies all of the following conditions:
- For each of the jewelry shops, the box contains one jewel purchased there.
- All of the following M restrictions are met.
- Restriction i (1 \leq i \leq M): (The size of the jewel purchased at Shop V_i)\leq (The size of the jewel purchased at Shop U_i)+W_i
Answer Q questions. In the i-th question, given an integer A_i, find the minimum total price of jewels that need to be purchased to make A_i good jewelry boxes. If it is impossible to make A_i good jewelry boxes, report that fact.
Constraints
- 1 \leq N \leq 30
- 1 \leq K_i \leq 30
- 1 \leq S_{i,j} \leq 10^9
- 1 \leq P_{i,j} \leq 30
- 1 \leq C_{i,j} \leq 10^{12}
- 0 \leq M \leq 50
- 1 \leq U_i,V_i \leq N
- U_i \neq V_i
- 0 \leq W_i \leq 10^9
- 1 \leq Q \leq 10^5
- 1 \leq A_i \leq 3 \times 10^{13}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Description of Shop 1 Description of Shop 2 \vdots Description of Shop N M U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M Q A_1 A_2 \vdots A_Q
The description of Shop i (1 \leq i \leq N) is in the following format:
K_i S_{i,1} P_{i,1} C_{i,1} S_{i,2} P_{i,2} C_{i,2} \vdots S_{i,K_i} P_{i,K_i} C_{i,K_i}
Output
Print Q lines. The i-th line should contain the minimum total price of jewels that need to be purchased to make A_i good jewelry boxes, or -1 if it is impossible to make them.
Sample Input 1
3 2 1 10 1 3 1 1 3 1 10 1 2 1 1 3 10 1 2 1 1 1 3 10 1 2 1 2 0 2 3 0 3 1 2 3
Sample Output 1
3 42 -1
Let (i,j) represent the j-th jewel sold at Shop i. The answer to each query is as follows:
- A_1=1: Making a box with (1,2),(2,2),(3,1) costs 1+1+1=3, which is optimal.
- A_2=2: Making a box with (1,1),(2,1),(3,1) and another with (1,2),(2,3),(3,2) costs (10+10+1)+(1+10+10)=42, which is optimal.
- A_3=3: We cannot make three good boxes.
Sample Input 2
5 5 86849520 30 272477201869 968023357 28 539131386006 478355090 8 194500792721 298572419 6 894877901270 203794105 25 594579473837 5 730211794 22 225797976416 842538552 9 420531931830 871332982 26 81253086754 553846923 29 89734736118 731788040 13 241088716205 5 903534485 22 140045153776 187101906 8 145639722124 513502442 9 227445343895 499446330 6 719254728400 564106748 20 333423097859 5 332809289 8 640911722470 969492694 21 937931959818 207959501 11 217019915462 726936503 12 382527525674 887971218 17 552919286358 5 444983655 13 487875689585 855863581 6 625608576077 885012925 10 105520979776 980933856 1 711474069172 653022356 19 977887412815 10 1 2 231274893 2 3 829836076 3 4 745221482 4 5 935448462 5 1 819308546 3 5 815839350 5 3 513188748 3 1 968283437 2 3 202352515 4 3 292999238 10 510266667947 252899314976 510266667948 374155726828 628866122125 628866122123 1 628866122124 510266667949 30000000000000
Sample Output 2
26533866733244 13150764378752 26533866733296 19456097795056 -1 33175436167096 52 33175436167152 26533866733352 -1