{"raw_statement":[{"iden":"background","content":"> 两年级生 孤单一人\n>\n> 仰望上空 陋市苍穹\n>\n> 在宇宙这个约会室中\n>\n> Maybe 我们只是刚好没能邂逅呢"},{"iden":"statement","content":"著名工程学专家 625OutContradiction 设计了一张地铁交通网 $G$．$G$ 拥有 $n$ 个站点和 $m$ 条地铁线路．\n\n第 $i$ 条地铁线路 $P_i$ 会经过交通网上的若干站点，形如 $P_i=(u_1,u_2,u_3,...,u_{k_i})(k_i>0)$：每两个相邻站点 $u_j,u_{j+1}(j<k_i)$ 之间存在一段属于线路 $i$ 的从 $u_j$ 通向 $u_{j+1}$ 的单向地铁轨道．保证一条地铁线路不重复经过同一站点．但一个站点可能被若干条地铁线路经过．\n\n丹羽和艾莉欧准备从 $1$ 号站点前往 $n$ 号站点．然而他们的自行车坏掉了，只好准备乘坐地铁．现在他们需要决定出行的方案．\n\n一种出行方案具体是这样的：从 $1$ 号站点出发，选定一条经过 $1$ 号站点的地铁线路并开始乘坐地铁．沿当前地铁线路乘坐地铁的过程中，可以选择换乘其他任意一条经过当前站点的地铁线路．要求最终到达 $n$ 号站点．乘坐地铁过程中重复经过某一站点或某段地铁轨道是被允许的．\n\n**请注意：从 $1$ 号站点出发，第一次乘坐地铁不被算作换乘．**\n\n艾莉欧提出了 $q$ 个问题．对于每个问题，艾莉欧会提供三个参数 $a, b, c$．在这次问题中，一个出行方案如果经过了 $x$ 段地铁轨道并进行了 $y$ 次换乘，那么它的疲惫值为 $ax+by$．您需要回答换乘次数不超过 $c$ 的出行方案中最小的疲惫值是多少．"},{"iden":"input","content":"第一行三个整数 $n, m, q$．\n\n接下来 $m$ 行，第 $i$ 行形如：$k_i,u_1,u_2,u_3,...,u_{k_i}$．\n表示一条地铁线路．\n\n接下来 $q$ 行，每行三个整数，表示 $a,b,c$．"},{"iden":"output","content":"$q$ 行，对应每个问题的回答．"},{"iden":"note","content":"### 样例 #1 说明\n$1\\rightarrow 2\\rightarrow 3\\rightarrow 4\\rightarrow 5$ 是给出的第一条地铁线路，$1\\rightarrow 3$，$2\\rightarrow 4\\rightarrow 5$ 是第二三条地铁线路．\n\n对于第一二组询问，均存在一种最优的出行方案为，在 $1$ 站点搭乘第二条地铁线路到达 $3$ 站点，在 $3$ 站点换乘第一条地铁线路到达终点；共经过 $3$ 段地铁轨道，并进行了 $1$ 次换乘，故第一二组询问的答案分别为 $3\\times 1+1\\times 1=4$，$3\\times 3+1\\times 0=9$．对于第三组询问，由于换乘的代价较大，最优的方案为顺着第一条地铁线路一直通向终点，途径 $4$ 段地铁轨道，答案为 $4$．\n\n### 数据点约束\n对于所有数据满足：\n\n$1\\le n \\le 10^5$，$1\\le m \\le 10^4$，$1\\le q \\le 10^5$，$\\sum k_i \\le 3\\times 10^5$．\n\n$0 \\le a,b \\le 10^6$，$0 \\le c \\le 20$．\n\n---\n对于 $10\\%$ 的数据满足：$n \\le 20$，$\\sum k_i \\le 40$，$q \\le 30$．\n\n---\n\n对于另外 $20\\%$ 的数据满足：$c=0$．\n\n---\n\n对于另外 $30\\%$ 的数据满足：$q=1$．\n\n---\n\n题目中可能存在只经过一个地铁站的地铁线路．这种线路可以直接忽视．数据保证：对于任意一组询问，存在一条合法的路线可以到达终点．"}],"translated_statement":null,"sample_group":[["5 3 3\n5 1 2 3 4 5\n2 1 3\n3 2 4 5\n1 1 1\n3 0 2\n1 5 2\n","4\n9\n4\n"],["10 7 10\n10 1 2 3 4 5 6 7 8 9 10\n5 3 8 5 1 6\n2 1 6\n4 3 7 8 5\n1 1\n2 10 2\n6 8 4 7 3 1 5\n5 10 6\n17 14 0\n11 14 5\n8 8 3\n8 13 9\n11 2 9\n7 1 6\n11 11 8\n15 3 0\n0 17 4\n","35\n153\n69\n48\n53\n57\n36\n66\n135\n0\n"],["10 7 10\n10 1 2 3 4 5 6 7 8 9 10\n3 2 7 1\n3 5 10 9\n2 2 7\n5 4 8 1 7 2\n3 10 9 4\n4 2 1 7 8\n18 6 0\n16 11 0\n18 1 0\n14 0 0\n19 14 0\n3 2 0\n18 15 0\n5 18 0\n2 17 0\n20 10 0\n","162\n144\n162\n126\n171\n27\n162\n45\n18\n180\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}