UVA1048 Low Cost Air Travel

题意翻译： 很多航空公司都会出售一种联票，要求从头坐，上飞机时上缴机票，可以在中途任何一站下飞机。比如，假设你有一张“城市$1$->城市$2$->城市$3$”的联票，你不能用来只从城市$2$飞到城市$3$（因为必须从头坐），也不能先从城市$1$飞到城市$2$再用其他票飞到其他城市玩，回到城市$2$后再用原来的机票飞到城市$3$（因为机票已经上缴）。 这里有一个例子。假设有3种票，每种票的情况如下所示： - 票1：城市$1$->城市$3$->城市$4$，票价$225$美元 - 票2：城市$1$->城市$2$，票价$200$美元 - 票3：城市$2$->城市$3$，票价$50$美元 你想从城市$1$飞到城市$3$，有两种方法可以选择。买票$1$，只飞第一段；买票$2$和$3$，通过城市$2$中转。显然，第一种方法比较省钱，虽然浪费了一段。 给出票的信息，以及一个或多个行程单，你的任务是买尽量少的票（同一种票可以买多张），使得总花费最小。输入保证行程总是可行的。行程单上的城市必须按顺序到达，但中间可以经过一些辅助城市。

输入包含多组数据。每组数据第一行为一个整数$NT$，即联票的种类数。以下$NT$行每行为一个联票描述，其中第一个整数为票的价格，然后是联票上城市的数目以及这些城市的整数编号（按顺序给出）。接下来为一个整数$NI$，即需要计算最小花费的行程单数目。以下$NI$行每行为一个行程单，其中一个整数为行程单上的城市数目（包括起始城市），以及这些城市的编号（按顺序给出）。输入保证每组数据最多包含$20$种联票和$20$个行程单，每张票或者行程单上有至少$2$个，最多$10$个城市。票价不超过$\$ 10000$。联票或者行程单上的相邻城市保证不同。票和行程单都从$1$开始编号。输入结束标志为$NT=0$。

对于每组数据的每张行程单，输出最小花费和对应的方案（按顺序，详见样例输出）。输出保证唯一。 样例输入： ``` 3 225 3 1 3 4 200 2 1 2 50 2 2 3 1 2 1 3 3 100 2 2 4 100 3 1 4 3 200 3 1 2 3 2 3 1 4 3 3 1 2 4 0 ``` 样例输出： ``` Case 1, Trip 1: Cost = 225 Tickets used: 1 Case 2, Trip 1: Cost = 100 Tickets used: 2 Case 2, Trip 2: Cost = 300 Tickets used: 3 1 ```