{"raw_statement":[{"iden":"problem statement","content":"There are $N$ jewelry shops numbered $1$ to $N$.\nShop $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.\nA jewelry box is said to be _good_ if it satisfies all of the following conditions:\n\n*   For each of the jewelry shops, the box contains one jewel purchased there.\n*   All of the following $M$ restrictions are met.\n    *   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$\n\nAnswer $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."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 30$\n*   $1 \\leq K_i \\leq 30$\n*   $1 \\leq S_{i,j} \\leq 10^9$\n*   $1 \\leq P_{i,j} \\leq 30$\n*   $1 \\leq C_{i,j} \\leq 10^{12}$\n*   $0 \\leq M \\leq 50$\n*   $1 \\leq U_i,V_i \\leq N$\n*   $U_i \\neq V_i$\n*   $0 \\leq W_i \\leq 10^9$\n*   $1 \\leq Q \\leq 10^5$\n*   $1 \\leq A_i \\leq 3 \\times 10^{13}$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\nDescription of Shop $1$\nDescription of Shop $2$\n$\\vdots$\nDescription of Shop $N$\n$M$\n$U_1$ $V_1$ $W_1$\n$U_2$ $V_2$ $W_2$\n$\\vdots$\n$U_M$ $V_M$ $W_M$\n$Q$\n$A_1$\n$A_2$\n$\\vdots$\n$A_Q$\n\nThe description of Shop $i$ ($1 \\leq i \\leq N$) is in the following format:\n\n$K_i$\n$S_{i,1}$ $P_{i,1}$ $C_{i,1}$\n$S_{i,2}$ $P_{i,2}$ $C_{i,2}$\n$\\vdots$\n$S_{i,K_i}$ $P_{i,K_i}$ $C_{i,K_i}$"},{"iden":"sample input 1","content":"3\n2\n1 10 1\n3 1 1\n3\n1 10 1\n2 1 1\n3 10 1\n2\n1 1 1\n3 10 1\n2\n1 2 0\n2 3 0\n3\n1\n2\n3"},{"iden":"sample output 1","content":"3\n42\n-1\n\nLet $(i,j)$ represent the $j$\\-th jewel sold at Shop $i$. The answer to each query is as follows:\n\n*   $A_1=1$: Making a box with $(1,2),(2,2),(3,1)$ costs $1+1+1=3$, which is optimal.\n*   $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.\n*   $A_3=3$: We cannot make three good boxes."},{"iden":"sample input 2","content":"5\n5\n86849520 30 272477201869\n968023357 28 539131386006\n478355090 8 194500792721\n298572419 6 894877901270\n203794105 25 594579473837\n5\n730211794 22 225797976416\n842538552 9 420531931830\n871332982 26 81253086754\n553846923 29 89734736118\n731788040 13 241088716205\n5\n903534485 22 140045153776\n187101906 8 145639722124\n513502442 9 227445343895\n499446330 6 719254728400\n564106748 20 333423097859\n5\n332809289 8 640911722470\n969492694 21 937931959818\n207959501 11 217019915462\n726936503 12 382527525674\n887971218 17 552919286358\n5\n444983655 13 487875689585\n855863581 6 625608576077\n885012925 10 105520979776\n980933856 1 711474069172\n653022356 19 977887412815\n10\n1 2 231274893\n2 3 829836076\n3 4 745221482\n4 5 935448462\n5 1 819308546\n3 5 815839350\n5 3 513188748\n3 1 968283437\n2 3 202352515\n4 3 292999238\n10\n510266667947\n252899314976\n510266667948\n374155726828\n628866122125\n628866122123\n1\n628866122124\n510266667949\n30000000000000"},{"iden":"sample output 2","content":"26533866733244\n13150764378752\n26533866733296\n19456097795056\n-1\n33175436167096\n52\n33175436167152\n26533866733352\n-1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}