TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

100.0% (22/22)

Submission's AC Ratio

51.9% (41/79)

Description

植物園高級中學是全國首屈一指的名校,其設立目的旨在培育肩負國家未來的重要人才。而這所中學的畢業生,無論是升學或是就業均有受到保障,要進入頂尖的大學或企業都易如反掌。

然而由於是高手的聚集地,這所學校內部的競爭壓力也是高的驚人。尤其是這所學校中途退學的機制,讓學生想要在這裡安然無事的度過三年畢業,可說是難如登天。

你是植物園高級中學的學生之一,而學校剛舉行了第一次的定期考試。這個考試有個特殊的規定,那就是只要一個學生有任何一個科目不及格,那麼他就得接受中途退學的懲罰。及格的定義是該科成績達全班成績平均值的一半。

你的班上有$N$位同學(包含你),編號為$1$到$N$,進行了一場總分為$C$分的定期考試,所有人的分數皆為$0$到$C$之間的整數。等到考試的成績一揭曉,就可能有人必須退學。

不過神通廣大的你,在分數正式公布前,早已事先得知了全班每個人的成績,其中第$i$號的人成績為$s_i$。而且根據你所知道的消息,在這所學校裡,有十萬零八千種以上的方法,可以讓一個人的分數上升或下降。當然,這麼做必須付出一定的代價,而且每個人的代價也不盡相同。根據你的資料,對於第$i$個人,使他的成績每上升一分,就必須付出$a_i$的代價;而使他的成績每下降一分,就必須付出$b_i$的代價。不過每個人的成績最後都必須落在$0$到$C$分之間,否則是不合法的。

你希望使全班的所有同學都平安度過這次的定期考試,但又不希望付出太多代價。求欲使所有人皆及格所需付出的代價最小值是多少。

Input Format

輸入的第一行有兩個整數$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$。

Output Format

輸出一個整數,表示使全班及格所需的最小花費。

Sample Input

3 100
20 100 80
6 5 4
3 2 1

Sample Output

85

Hints

對於範例測資,代價最小的方案如下:將第一個人提高$5$分,並將第三個人降低$55$分,所需代價為$5\times 6+55\times 1=85$。

Problem Source

110學年度建國中學校內資訊能力競賽初試pE

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 131072 65536 1 2 3 4
1 1500 131072 65536 1 2 3 4
2 1500 131072 65536 1 2 3 4
3 1500 131072 65536 1 2 3 4
4 1500 131072 65536 1 2 3 4
5 1500 131072 65536 1 2 3 4
6 1500 131072 65536 1 2 3 4
7 1500 131072 65536 1 2 3 4
8 1500 131072 65536 1 2 3 4
9 1500 131072 65536 1 2 3 4
10 1500 131072 65536 1 2 3 4
11 1500 131072 65536 1 2 3 4
12 1500 131072 65536 1 2 3 4
13 1500 131072 65536 1 2 3 4
14 1500 131072 65536 1 2 3 4
15 1500 131072 65536 1 2 3 4
16 1500 131072 65536 1 2 3 4
17 1500 131072 65536 2 3 4
18 1500 131072 65536 2 3 4
19 1500 131072 65536 2 3 4
20 1500 131072 65536 2 3 4
21 1500 131072 65536 2 3 4
22 1500 131072 65536 2 3 4
23 1500 131072 65536 2 3 4
24 1500 131072 65536 2 3 4
25 1500 131072 65536 2 3 4
26 1500 131072 65536 2 3 4
27 1500 131072 65536 2 3 4
28 1500 131072 65536 2 3 4
29 1500 131072 65536 2 3 4
30 1500 131072 65536 2 3 4
31 1500 131072 65536 2 3 4
32 1500 131072 65536 3 4
33 1500 131072 65536 3 4
34 1500 131072 65536 3 4
35 1500 131072 65536 3 4
36 1500 131072 65536 3 4
37 1500 131072 65536 3 4
38 1500 131072 65536 3 4
39 1500 131072 65536 3 4
40 1500 131072 65536 3 4
41 1500 131072 65536 3 4
42 1500 131072 65536 3 4
43 1500 131072 65536 3 4
44 1500 131072 65536 3 4
45 1500 131072 65536 3 4
46 1500 131072 65536 3 4
47 1500 131072 65536 4
48 1500 131072 65536 4
49 1500 131072 65536 4
50 1500 131072 65536 4
51 1500 131072 65536 4
52 1500 131072 65536 4
53 1500 131072 65536 4
54 1500 131072 65536 4
55 1500 131072 65536 4
56 1500 131072 65536 4
57 1500 131072 65536 4
58 1500 131072 65536 4
59 1500 131072 65536 4
60 1500 131072 65536 4
61 1500 131072 65536 4
62 1500 131072 65536 4
63 1500 131072 65536 4
64 1500 131072 65536 4
65 1500 131072 65536 4
66 1500 131072 65536 4