描述

约翰要去钓鱼。他有$h$小时可用（$1 \leq h \leq 16$），该区域内有$n$个湖（$2 \leq n \leq 25$），所有湖都可通过一条单向道路到达。约翰从湖$1$出发，但他可以在任意一个湖结束行程。他只能从一个湖前往下一个湖，不过除非他想停在某个湖，否则不必在每个湖都停留。对于每个$i = 1, \ldots, n - 1$，从湖$i$到湖$i + 1$所需的$5$分钟间隔数记为$t_i$（$0 < t_i \leq 192$）。例如，$t_3 = 4$表示从湖$3$到湖$4$需要$20$分钟。为了帮助规划他的钓鱼行程，约翰收集了一些关于这些湖的信息。对于每个湖$i$，初始$5$分钟内预计钓到的鱼的数量记为$f_i$（$f_i \geq 0$）。每钓鱼$5$分钟，下一个$5$分钟间隔内预计钓到的鱼的数量会以固定速率$d_i$（$d_i \leq 0$）减少。如果一个间隔内预计钓到的鱼的数量小于或等于$d_i$，那么下一个间隔这个湖里就没有鱼可钓了。为了简化规划，约翰假设没有其他人在这些湖钓鱼来影响他预计钓到的鱼的数量。

输入

输入中会给出多个测试用例。每个测试用例以包含$n$的一行开始。接下来是包含$h$的一行。然后是包含$n$个整数的一行，指定$f_i$（$1 \leq i \leq n$），接着是包含$n$个整数的一行，指定$d_i$（$1 \leq i \leq n$），最后是包含$n - 1$个整数的一行，指定$t_i$（$1 \leq i \leq n - 1$）。当$n = 0$时，输入结束。

输出

对于每个测试用例，打印在每个湖花费的分钟数，用逗号分隔，这是能钓到最多鱼的计划（即使一行超过$80$个字符，也应将整个计划打印在一行上）。接下来是包含预计钓到的鱼的数量的一行。

如果存在多个计划，选择在湖$1$停留时间尽可能长的那个计划，即使在某些间隔预计钓不到鱼。如果仍然有平局，选择在湖$2$停留时间尽可能长的计划，以此类推。在每个测试用例之间插入一个空行。

2 
1 
10 1 
2 5 
2 
4 
4 
10 15 20 17 
0 3 4 3 
1 2 3 
4 
4 
10 15 50 30 
0 3 4 3 
1 2 3 
0 

45, 5 
Number of fish expected: 31 

240, 0, 0, 0 
Number of fish expected: 480 

115, 10, 50, 35 
Number of fish expected: 724 

来源

1999年中北美东部地区竞赛