UOJ Logo

NOI.AC

1S 512MB
统计

甜品囤积者(2)

时间限制:1秒,内存限制:128MB 读入文件名:moredessert.in 输出文件名:moredessert.out

【题目描述】

放假在家,甜品总是少不了的。

最近你已经瞄中了一家甜品店的甜品,打算接下来连续$n$天都要吃那里的甜品了。甜品店已经知道你想要囤积甜品了!于是店主决定,根据你在那天之前囤积的甜品袋数$x$(即在之前剩余没有吃完的甜品袋数),第i天每袋甜品的价格是$a_i x^2+b_i x+c_i$。而你也计划好了每天要吃的甜品袋数,第$i$天要吃$s_i$袋甜品。

每天你都可以买任意多袋甜品,吃不完可以囤积着并不用担心过期变质,那么为了满足$n$天的甜品需求,你至少要花费多少钱呢。

【输入格式】

输入共$5$行。

第一行输入一个正整数$n$,表示天数。

第二行输入$n$个整数,表示第$1$天到第$n$天的甜品价格函数中的$a_i$,输入用一个空格分隔。

第三行输入$n$个整数,表示第$1$天到第$n$天的甜品价格函数中的$b_i$,输入用一个空格分隔。

第四行输入$n$个整数,表示第$1$天到第$n$天的甜品价格函数中的$c_i$,输入用一个空格分隔。

第五行输入$n$个整数,表示第$1$天到第$n$天计划要吃的甜品袋数$s_i$,输入用一个空格分隔。

【输出格式】

输出共一行,包含一个整数,表示最小花费。

【输入输出样例1】

moredessert.in

5

0 0 0 0 0

0 0 0 0 0

9 2 9 5 3

5 3 10 6 5

moredessert.out

93

【输入输出样例2】

moredessert.in

5

0 0 0 0 0

10 3 7 3 5

4 8 8 1 6

10 2 9 4 9

moredessert.out

97

【输入输出样例3】

moredessert.in

5

3 5 2 8 10

-3 -6 -2 -2 -2

10 7 10 7 1

6 5 2 4 7

moredessert.out

137

【数据规模与约定】

对于前30%的数据,$a_i=b_i=0$,$1≤c_i≤1000$;

对于前60%的数据,$a_i=0$,$1≤b_i,c_i≤1000$;

对于100%的数据,$1≤n≤100$,$0≤a_i,c_i≤1000$,$-1000≤b_i≤1000$,价格函数在$x≥0$的情况下必定为正数,$\sum s_i≤1000$。