1780 . 奇異熱狗(KIWI)
TopCoder
Tags
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 1
5 10 3
1 1 4 1 7
7 8 6 2 3
1 1 4 1 7
7 8 6 2 3
Sample Output 1
62
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
12 18 16 14 1 5 17 1 1 8
11 5 9 7 5 5 2 11 18 7
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 |