我不会做
题目描述
小明想在暑假里自己开车回家,顺带进行短途的旅行,现在他有一辆油缸容量为L 单位的汽车,他的学校在 1 号点,家在 n 号点。把起点和终点计算在内,依次会经过 n 个城市。从第 i 号城市到 i+1 号城市需要消耗 Wi的油量,并且不能往回开(不能从 i+1 号城市开回到 i 号城市)。但是小明是个小机灵鬼,他发现每个城市的油价都不一样,这意味着需要有准备地规划自己应当在哪个城市加多少油。更有意思的是,他发现这 n 所城市都可以进行油价的自由买卖。在城市 i,如果每单位的购买油价为 Ci,那么每单位的售卖油价就为 0.95*Ci。当然小明不能太过于贪心,他只能把油放在油缸里,而不能放进瓶子或者罐子里,因为那样太危险。
现在小明有 m 单位的钱,请问到目的地最多还能够剩下多少钱?注意途中小明不能够欠钱!如果途中小明开不到终点,那么请输出-1。
输入
从文件 car.in 中读入数据。
输入一共有 3 行,第一行依次为 n(城市数量), m(初始钱数), L(油缸容量)。其中 n≤300,m≤10^9,L≤400。
第二行包含 n-1 个整数 Wi(1≤Wi≤400)。
第三行包含 n 个整数 Ci(1≤Ci≤10^9)。
输出
输出到文件 car.out 中。
输出共一行,保留两位小数,表示最后最多剩下多少钱。如果小明中途是在没有钱开回到家里,则输出-1。
样例输入 复制
样例输入1
3 100 12
5 5
9 20 10
样例输入2
3 100 5
5 5
9 100 10
样例输出 复制
样例输出1
20.00
样例输出2
-1
数据范围限制
对 30%的数据,n<8, L<8。
对 70%的数据,n<100, L<100。
提示
对于样例 1,在 1 号城市购买 11 升油消费 99,在 2 号城市卖掉 1 升, 盈利20*0.95=19,最终开到终点 3 号城市。所以最终剩下的钱数是 100-99+19=20