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

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10