/ 
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