TopCoder

WeaK
weak.infor.org 雖然這裡好像沒什麼東西。

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

15.6% (5/32)

Description

知名的航空公司CK Airlines向來以個人化服務以及美味的餐點聞名。在機上的一切事務都是客製化的,其中機上送餐的時間也是客製化的。每位乘客可以自由選擇拿到餐點的時間。

CK Airlines的機上餐點中,有一道特別出名的餐點:牛排。CK Airlines的牛排除了牛排之外還有配菜,所以製作牛排時需要準備配菜以及煎煮牛排。CK Airlines的配菜以及牛排都是頂級的,兩者的味道相輔相成,形成了多層次高級的口味以及觸感,實為一夢幻料理。而經過許久的磨練後,不論是準備配菜或煎煮牛排,機上的廚師都可以在一分鐘內處理好。儘管廚師大可在飛機飛穩後開始將所有需要的牛排煮好,但是CK Airlines不希望乘客拿到的牛排是冷掉的,所以CK Airlines要求每塊牛排煎煮完畢後都要隨著準備好的配菜馬上送到客人面前。然而CK Airlines不希望上菜時間離乘客期望的時間差距超過$x$分鐘,也不希望牛排在客人期望的時間後才上。換句話說,假設在第$a$分鐘時將牛排及配菜送給客人,而客人要求拿到餐點的時間是第$b$分鐘,那麼$a$和$b$必須滿足$a\leq b\leq a+x$。此外,儘管牛排一煎好就要送給客人,但是配菜則不受此限制。

高品質的CK Airlines的要求可不只這樣。由於CK Airlines標榜著他們是個重視環保的航空,因此他們希望減少開火的總時間。而不論是解凍或是煎煮,都需要開火才能執行。為了有效減少開火的總時間,機上共有$k$個處理食物的地方,只要在開火的時間,$k$個地方都可以同時進行準備一份配菜或煎煮一塊牛排其一程序($k$個地方所進行的程序不需要相同)。

相信讀到這裡,你已經知道CK Airlines的要求有多高了。高品質、重視客製化程序、環保、以及高要求的CK Airlines理所當然地希望在前述的所有條件下再最小化開火的總時間。然而飛機上乘客眾多,因此CK Airlines希望能編寫出一支能幫忙維持高品質的程式,幫助他們找出最佳的處理牛排的程序。注意:所有程序都只能從飛機飛穩後開始,並且不限制開火時間需 連續。

Input Format

本題為單筆輸入。
第一行有三個非負整數$n,x,k$,分別代表機上乘客人數,送餐容許誤差時間以及機上可處理食物的地方數。
第二行有$n$個正整數$2\leq t_1, t_2, \dots, t_n$,分別代表第$1, 2, \dots, n$位乘客希望在飛機飛穩後第$t_1, t_2, \dots, t_n$分鐘拿到牛排。

Output Format

請輸出一個正整數,代表總開火時間的最小值。若不論如何都無法達成目標,請輸出-1。

Sample Input

輸入範例1:
4 1 2
2 2 3 2

輸入範例2:
5 1 3
2 2 5 5 6

Sample Output

輸出範例1:
-1

輸出範例2:
4

Hints

本題共有五組測試資料。每組可有多個輸入檔案,全部答對該組才得分。

第一組10分,$1= k\leq n\leq 3 ,x,t_i\leq 12$
第二組15分,$1\leq k\leq n\leq 50, x=0,t_i\leq 2000$
第三組15分,$k=1,n\leq 50, x,t_i\leq 2000$
第四組30分,$1\leq k\leq n\leq 30 ,x,t_i\leq 30$
第五組30分,$1\leq k\leq n\leq 50, x,t_i\leq 2000$

Problem Source

Problem Set / Description by Paupière
建國中學105學年度全國賽模擬賽pC

Subtasks

No. Testdata Range Score
1 0~4 10
2 5~11 15
3 12~16 15
4 17~23 30
5 24~32 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 65536 262144 1
1 500 65536 262144 1
2 500 65536 262144 1
3 500 65536 262144 1
4 500 65536 262144 1
5 500 65536 262144 2
6 500 65536 262144 2
7 500 65536 262144 2
8 500 65536 262144 2
9 500 65536 262144 2
10 500 65536 262144 2
11 500 65536 262144 2
12 500 65536 262144 3
13 500 65536 262144 3
14 500 65536 262144 3
15 500 65536 262144 3
16 500 65536 262144 3
17 500 65536 262144 4
18 500 65536 262144 4
19 500 65536 262144 4
20 500 65536 262144 4
21 500 65536 262144 4
22 500 65536 262144 4
23 500 65536 262144 4
24 500 65536 262144 5
25 500 65536 262144 5
26 500 65536 262144 5
27 500 65536 262144 5
28 500 65536 262144 5
29 500 65536 262144 5
30 500 65536 262144 5
31 500 65536 262144 5
32 500 65536 262144 5