TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

50.0% (1/2)

Description

Surwigo 最近開了一個新的工廠--奇異公司,

主要是要把奇異果加工製成奇異狗(奇異果口味的熱狗)。

其運作方式如下:

一開始會接到許多的訂單,代表每天需要出口奇異狗的量。

當然,沒有奇異果當材料是無法做出奇異狗的,所以奇異公司必頇要適時的花錢買進奇異果。

我們可以先假設一個奇異果恰好可以加工成一根奇異狗,而且當天拿到的材料當天就可以製成奇異狗並且出售。

但是不論是奇異果或是奇異狗都不能放在室溫下超過一天,如果想要保存就必頇花費一些冷藏的費用。

當然冷藏保存也是有期限,一旦超過 T 天,奇異果或奇異狗就會壞掉。

身為奇異公司專業顧問的你,打算分析一下奇異公司對於接下來幾天的開銷最少是多少,因此找了接下來 N 天的資料:

每天的訂單數量(A1...An 根)

每天購買一顆奇異果要花多少錢(C1...Cn 元)

還有每天冷藏一顆奇異果或奇異狗要花多少錢(S 元),

與奇異果跟奇異狗的保存期限(T 天)。

問你在滿足所有訂單需求的情況下,最低花費是多少?

Input Format

輸入包含三行,第一行有三個數 N,T,S,分別代表接下來有 N 天的資料,奇異果/狗的保存期限,與每天冷藏一顆奇異果/狗要多少錢。
1≤N, T≤1000000, S≤1000
第二行包含 N 個數,代表 A1,A2,...,An,代表每天的訂單數量。
0≤Ai≤1000
第三行包含 N 個數,代表 C1,C2,...,Cn,代表每天買一顆奇異果要多少錢。
1≤Ci≤1000

Output Format

輸出一個數,代表在滿足以上訂單的情況下,至少要花多少錢。

Sample Input

Sample Input 1:
5 10 3
1 1 4 1 7
7 8 6 2 3

Sample Input 2:
10 3 20
12 18 16 14 1 5 17 1 1 8
11 5 9 7 5 5 2 11 18 7

Sample Output

Sample Output 1:
62

Sample Output 2:
613

Hints

Problem Source

原TIOJ1780 / 99建中校內資訊能力競賽(prob5)

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 10000 65536
1 10000 65536
2 10000 65536
3 10000 65536
4 10000 65536
5 10000 65536
6 10000 65536
7 10000 65536
8 10000 65536
9 10000 65536