Bessie 的花园中有 株植物，从左到右编号为 到 （）。Bessie 知道植物 至少需要 （）单位的水。
Bessie 有一个十分古怪的灌溉系统，包含 条水渠，编号为 到 。每条水渠 有一个相关的单位费用 （），Bessie 可以支付费用 来为植物 和 各提供 单位的水，其中 是一个非负整数。
Bessie 很忙，可能没有时间使用所有的水渠。对于每一个 ，计算仅使用前 条水渠灌溉植物 到 所需要的最小费用。
输入的第一行包含一个正整数 。
第二行包含 个空格分隔的整数 。
第三行包含 个空格分隔的整数 。
输出 行，每行包含一个整数。第 行包含使用前 条水渠灌溉前 株植物的最小费用。
3 39 69 33 30 29
2070 2127
3 33 82 36 19 1
1558 676
8 35 89 44 1 35 3 62 50 7 86 94 62 63 9 49
623 4099 4114 6269 6272 6827 8827
样例 1 解释：
使用第一条水渠灌溉前 株植物的最小费用是通过使用第一条水渠 次，支付 。
灌溉前 株植物的最小费用是通过使用第一条水渠 次，第二条水渠 次，支付 。