题目描述

POJ 1042

已知在一条水平路边，有 $\red{n（2≤n≤25）}$个池塘，从左到右编号为$\red{1，2，3，…，n}$。小光有$\red{H（1≤H≤16）}$个小时的空闲时间，他只能从第一个池塘开始向右走，可以在每个池塘中钓鱼，每个池塘第一个$\red{5}$分钟可以钓到鱼$\red{f_i}$，以后再每钓$\red{5}$分钟，鱼量减少$\red{d_i}$，且从池塘到下一个池塘之间都有一定的距离$\red{5×}$$\red{t_i}$，例如$\red{t_i}$$\red{＝4}$，则距离为$\red{20}$。知道了每个池塘走到下一个池塘的时间和每个池塘一开始能够钓鱼的数量，求在规定的时间内所能钓到的最多的鱼的数量。

输入格式

有多组测试数据，每组数据第一行为整数$\red{n}$。第二行为$\red{H}$，随后一行为$\red{f_i}$ $\red{(1≤i≤n)}$， 接下来一行为$\red{d_i}$$\red{（1≤i≤n）}$，最后为$\red{n－1}$个整数$\red{t_i}$$\red{（1≤i≤n－1），n＝0}$表示结束。

输出格式

对于每组数据，第一行输出在每个池塘花费的时间，第二行输出钓到的最多鱼的数量。若有多种方案，选择在第一个池塘花费时间最多的方案，若第一个池塘没有钓到鱼，则选择在第二个池塘花费时间最多的方案，以此类推。每组方案以空行间隔。

样例

输入样例

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