#agc043f. [agc043_f]Jewelry Box

[agc043_f]Jewelry Box

Problem Statement

There are NN jewelry shops numbered 11 to NN.

Shop ii (1leqileqN1 \\leq i \\leq N) sells KiK_i kinds of jewels. The jj-th of these jewels (1leqjleqKi1 \\leq j \\leq K_i) has a size and price of Si,jS_{i,j} and Pi,jP_{i,j}, respectively, and the shop has Ci,jC_{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 MM restrictions are met.
    • Restriction ii (1leqileqM1 \\leq i \\leq M): ((The size of the jewel purchased at Shop ViV_i)leq()\\leq (The size of the jewel purchased at Shop UiU_i)+Wi)+W_i

Answer QQ questions. In the ii-th question, given an integer AiA_i, find the minimum total price of jewels that need to be purchased to make AiA_i good jewelry boxes. If it is impossible to make AiA_i good jewelry boxes, report that fact.

Constraints

  • 1leqNleq301 \\leq N \\leq 30
  • 1leqKileq301 \\leq K_i \\leq 30
  • 1leqSi,jleq1091 \\leq S_{i,j} \\leq 10^9
  • 1leqPi,jleq301 \\leq P_{i,j} \\leq 30
  • 1leqCi,jleq10121 \\leq C_{i,j} \\leq 10^{12}
  • 0leqMleq500 \\leq M \\leq 50
  • 1leqUi,VileqN1 \\leq U_i,V_i \\leq N
  • UineqViU_i \\neq V_i
  • 0leqWileq1090 \\leq W_i \\leq 10^9
  • 1leqQleq1051 \\leq Q \\leq 10^5
  • 1leqAileq3times10131 \\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:

NN Description of Shop 11 Description of Shop 22 vdots\\vdots Description of Shop NN MM U1U_1 V1V_1 W1W_1 U2U_2 V2V_2 W2W_2 vdots\\vdots UMU_M VMV_M WMW_M QQ A1A_1 A2A_2 vdots\\vdots AQA_Q

The description of Shop ii (1leqileqN1 \\leq i \\leq N) is in the following format:

KiK_i Si,1S_{i,1} Pi,1P_{i,1} Ci,1C_{i,1} Si,2S_{i,2} Pi,2P_{i,2} Ci,2C_{i,2} vdots\\vdots Si,KiS_{i,K_i} Pi,KiP_{i,K_i} Ci,KiC_{i,K_i}

Output

Print QQ lines. The ii-th line should contain the minimum total price of jewels that need to be purchased to make AiA_i good jewelry boxes, or \-1\-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)(i,j) represent the jj-th jewel sold at Shop ii. The answer to each query is as follows:

  • A1=1A_1=1: Making a box with (1,2),(2,2),(3,1)(1,2),(2,2),(3,1) costs 1+1+1=31+1+1=3, which is optimal.
  • A2=2A_2=2: Making a box with (1,1),(2,1),(3,1)(1,1),(2,1),(3,1) and another with (1,2),(2,3),(3,2)(1,2),(2,3),(3,2) costs (10+10+1)+(1+10+10)=42(10+10+1)+(1+10+10)=42, which is optimal.
  • A3=3A_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