User's AC Ratio

58.8% (10/17)

Submission's AC Ratio

14.6% (53/363)

Description

你聽過希爾伯特的旅館嗎?

希爾伯特最近在他的旅館裡面建造了一個無限長且有無限層的書架,因為他無限的房客離開時常把書忘在房間裡,時間久了就留下了無限難以整理的書。
雖然這些書都已經編號好了,但整理無限本書仍然太累了,所以他決定先把其中的$N$本書放上書架,試試這個書架好不好用。這$N$本書編號為1~$N$,其中編號$i$的書寬度為$A_i$。

具體來說,他希望能把書放進書架上的某些層,使得每一層的書編號都要連續且照順序排。另外,希爾伯特希望一眼就看出這層放了什麼書,因此他要求如果編號$i$和編號$i+1$的書放在同一層,那麼它們之間要放一個寬度為$L_i$的隔板。

因為每一本書的寬度都不同,希爾伯特希望他放書能放整齊一點。具體來說,他希望每一層擺出來的寬度都盡量是$K$。所謂「盡量」的意思,就是如果某一層書擺出來的實際寬度(包含書與隔板的寬度)是$M$,定義這層的「混亂度」就是$|M-K|^ P$(其中$P$是正整數),那他希望總混亂度(有放書的每一層混亂度加起來)最小。

但是,希爾伯特看不出來要怎麼分層會最整齊。所以請你先告訴他,在所有可能的擺書方式中,總混亂度的最小值是多少。

Input Format

第一行有三個正整數$N, K, P$。
第二行有$N$個正整數$A_1, A_2,\cdots ,A_N$。
第三行有$N-1$個非負整數$L_1, L_2,\cdots ,L_{N-1}$。
這些數的意義請參考題目敘述。

對於所有的測資,$N\leq 10^ 6; K\leq 10^ 9; P\leq 20; A_i, L_i\leq 10^ 9$。
保證答案絕對不會超過$10^ {18}$。

子任務(測資) 額外限制 分數
1 (0~3) $N\leq 20$ 37
2 (0~7) $N\leq 300$ 8
3 (0~9) $N\leq 2500$ 34
4 (0~11) $N\leq 12000$ 21
5 (12~15) $N\leq 4\times 10^ 5,K\leq 200$ 33
6 (16~19) $P\leq 2$ 80
7 (16~23) $P\leq 4$ 72
8 (0~27) 無限制 15

Output Format

請輸出一個非負整數,代表所有可能的擺書方式中總混亂度的最小值。

Sample Input

8 9 2
3 3 2 1 2 9 5 2
3 5 1 4 6 0 1

Sample Output

2

Hints

範例測資中,編號1, 2擺一層(寬度9)、3~5擺一層(寬度10)、6擺一層(寬度9)、7, 8擺一層(寬度8)。此時總混亂度為$0^ 2+1^ 2+0^ 2+1^ 2=2$。

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校隊補選pE

題目改編自NOI 2009

Subtasks

For Testdata: 0 ~ 3, Score: 37
For Testdata: 0 ~ 7, Score: 8
For Testdata: 0 ~ 9, Score: 34
For Testdata: 0 ~ 11, Score: 21
For Testdata: 12 ~ 15, Score: 33
For Testdata: 16 ~ 19, Score: 80
For Testdata: 16 ~ 23, Score: 72
For Testdata: 0 ~ 27, Score: 15
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 131072 262144
1 900 131072 262144
2 900 131072 262144
3 900 131072 262144
4 900 131072 262144
5 900 131072 262144
6 900 131072 262144
7 900 131072 262144
8 900 131072 262144
9 900 131072 262144
10 900 131072 262144
11 900 131072 262144
12 10000 131072 262144
13 900 131072 262144
14 900 131072 262144
15 1400 131072 262144
16 1900 131072 262144
17 1900 131072 262144
18 1900 131072 262144
19 1900 131072 262144
20 1900 131072 262144
21 1900 131072 262144
22 1900 131072 262144
23 1900 131072 262144
24 600 131072 262144
25 600 131072 262144
26 600 131072 262144
27 600 131072 262144