植物園高級中學是全國首屈一指的名校,其設立目的旨在培育肩負國家未來的重要人才。而這所中學的畢業生,無論是升學或是就業均有受到保障,要進入頂尖的大學或企業都易如反掌。
然而由於是高手的聚集地,這所學校內部的競爭壓力也是高的驚人。尤其是這所學校中途退學的機制,讓學生想要在這裡安然無事的度過三年畢業,可說是難如登天。
你是植物園高級中學的學生之一,而學校剛舉行了第一次的定期考試。這個考試有個特殊的規定,那就是只要一個學生有任何一個科目不及格,那麼他就得接受中途退學的懲罰。及格的定義是該科成績達全班成績平均值的一半。
你的班上有$N$位同學(包含你),編號為$1$到$N$,進行了一場總分為$C$分的定期考試,所有人的分數皆為$0$到$C$之間的整數。等到考試的成績一揭曉,就可能有人必須退學。
不過神通廣大的你,在分數正式公布前,早已事先得知了全班每個人的成績,其中第$i$號的人成績為$s_i$。而且根據你所知道的消息,在這所學校裡,有十萬零八千種以上的方法,可以讓一個人的分數上升或下降。當然,這麼做必須付出一定的代價,而且每個人的代價也不盡相同。根據你的資料,對於第$i$個人,使他的成績每上升一分,就必須付出$a_i$的代價;而使他的成績每下降一分,就必須付出$b_i$的代價。不過每個人的成績最後都必須落在$0$到$C$分之間,否則是不合法的。
你希望使全班的所有同學都平安度過這次的定期考試,但又不希望付出太多代價。求欲使所有人皆及格所需付出的代價最小值是多少。
輸入的第一行有兩個整數$N,C$,分別表示全班的總人數以及考試的總分。
接下來一行有$N$個整數$s_1,s_2,...,s_N$,$s_i$表示第$i$個人的分數。
接下來一行有$N$個整數$a_1,a_2,...,a_N$,$a_i$表示使第$i$個人的分數上升一分所需的代價。
接下來一行有$N$個整數$b_1,b_2,...,b_N$,$b_i$表示使第$i$個人的分數下降一分所需的代價。
對於所有測試資料,保證$1\leq N\leq 10^ 5$,$1\leq C\leq 5\times10^ 8$,$0\leq s_i\leq C$,$1\leq a_i,b_i\leq 10^ 5$。
輸出一個整數,表示使全班及格所需的最小花費。
對於範例測資,代價最小的方案如下:將第一個人提高$5$分,並將第三個人降低$55$分,所需代價為$5\times 6+55\times 1=85$。
110學年度建國中學校內資訊能力競賽初試pE
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~16 | $N, C \leq 100$ | 10 |
2 | 0~31 | $N, C \leq 1000$ | 16 |
3 | 0~46 | $C \leq 5 \times 10^ 5$ | 29 |
4 | 0~66 | 無其他限制 | 45 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1500 | 131072 | 65536 | |
1 | 1500 | 131072 | 65536 | |
2 | 1500 | 131072 | 65536 | |
3 | 1500 | 131072 | 65536 | |
4 | 1500 | 131072 | 65536 | |
5 | 1500 | 131072 | 65536 | |
6 | 1500 | 131072 | 65536 | |
7 | 1500 | 131072 | 65536 | |
8 | 1500 | 131072 | 65536 | |
9 | 1500 | 131072 | 65536 | |
10 | 1500 | 131072 | 65536 | |
11 | 1500 | 131072 | 65536 | |
12 | 1500 | 131072 | 65536 | |
13 | 1500 | 131072 | 65536 | |
14 | 1500 | 131072 | 65536 | |
15 | 1500 | 131072 | 65536 | |
16 | 1500 | 131072 | 65536 | |
17 | 1500 | 131072 | 65536 | |
18 | 1500 | 131072 | 65536 | |
19 | 1500 | 131072 | 65536 | |
20 | 1500 | 131072 | 65536 | |
21 | 1500 | 131072 | 65536 | |
22 | 1500 | 131072 | 65536 | |
23 | 1500 | 131072 | 65536 | |
24 | 1500 | 131072 | 65536 | |
25 | 1500 | 131072 | 65536 | |
26 | 1500 | 131072 | 65536 | |
27 | 1500 | 131072 | 65536 | |
28 | 1500 | 131072 | 65536 | |
29 | 1500 | 131072 | 65536 | |
30 | 1500 | 131072 | 65536 | |
31 | 1500 | 131072 | 65536 | |
32 | 1500 | 131072 | 65536 | |
33 | 1500 | 131072 | 65536 | |
34 | 1500 | 131072 | 65536 | |
35 | 1500 | 131072 | 65536 | |
36 | 1500 | 131072 | 65536 | |
37 | 1500 | 131072 | 65536 | |
38 | 1500 | 131072 | 65536 | |
39 | 1500 | 131072 | 65536 | |
40 | 1500 | 131072 | 65536 | |
41 | 1500 | 131072 | 65536 | |
42 | 1500 | 131072 | 65536 | |
43 | 1500 | 131072 | 65536 | |
44 | 1500 | 131072 | 65536 | |
45 | 1500 | 131072 | 65536 | |
46 | 1500 | 131072 | 65536 | |
47 | 1500 | 131072 | 65536 | |
48 | 1500 | 131072 | 65536 | |
49 | 1500 | 131072 | 65536 | |
50 | 1500 | 131072 | 65536 | |
51 | 1500 | 131072 | 65536 | |
52 | 1500 | 131072 | 65536 | |
53 | 1500 | 131072 | 65536 | |
54 | 1500 | 131072 | 65536 | |
55 | 1500 | 131072 | 65536 | |
56 | 1500 | 131072 | 65536 | |
57 | 1500 | 131072 | 65536 | |
58 | 1500 | 131072 | 65536 | |
59 | 1500 | 131072 | 65536 | |
60 | 1500 | 131072 | 65536 | |
61 | 1500 | 131072 | 65536 | |
62 | 1500 | 131072 | 65536 | |
63 | 1500 | 131072 | 65536 | |
64 | 1500 | 131072 | 65536 | |
65 | 1500 | 131072 | 65536 | |
66 | 1500 | 131072 | 65536 |