TopCoder

Thumb 12235114 p0 master1200
好色喔
希望明天會更好

User's AC Ratio

58.3% (7/12)

Submission's AC Ratio

9.0% (26/289)

Description

盩僰麌,一名來自大陸的競程選手,平時除了打開電腦在各大Judge上刷一排排綠色的AC以外,並沒有其他特別的嗜好。

盩僰麌居住的地方有著和常人不一樣的時間度量方法,也就是說,他們口中的一個禮拜其實是正常人所認為的$K$天。
「又是一個無趣的禮拜」盩僰麌一邊看著題目一邊心想,的確,解題對他來說已經太容易,甚至有點索然無味了。雖然一直切題不是什麼吸引人的事,為了不讓自己看起來很頹,還是希望可以每天都寫一些題目。於是他打開電腦,選了$N$道題目,並把每道題目的難易程度量化,第$i$道題的難度是$d_i$。

盩僰麌刷題的原則相當簡單,每天可以選任意的題目量來做,可是每天都至少要寫一題,此外,為了避免自己搞錯題目的編號,他決定順著前一天的題號做下去,並且每次都做編號連續的一串題目(也就是說,第一天從編號$1$的開始寫,而對於第$i$天,若第$i$天做的第一題及最後一題的題號分別是$s_i, t_i$,則$s_i = t_{i - 1} + 1(i > 1)$)。盩僰麌想要在刷題中還是盡可能尋找一些樂趣,對於每一天,他會從他做的第$i$題(假設編號為$x$)中得到$(C - i) \times d_x $的樂趣(由於一直刷題也會感到無趣厭惡,因此$C-i$可能為負的),而一整天的樂趣就是這天刷的每一題帶給他的樂趣總和。

在刷題的同時,盩僰麌還想要同時跟大家裝弱,宣稱自己其實一整天都在耍廢。群眾的目光是銳利的,他們會翻閱盩僰麌的Submission並找出AC最多題目的一天(假設那天刷了$Y$題)用以衡量盩僰麌的裝弱虛實,此時若盩僰麌宣稱自己一個禮拜每天刷的題數都小於$Y$的話,他的裝弱便會被識破。

兼顧刷題樂趣跟裝弱帶來的喜悅是非常重要的,請你告訴盩僰麌,在他一個禮拜刷題總樂趣至少$R$的情況下,他最多能裝得多弱(也就是他最少能說自己每天寫的題數都不超過多少)。

Input Format

第一行包含三個正整數$N, K, R, C$,代表總題數、大陸一星期有幾天、盩僰麌至少要獲得多少樂趣以及決定樂趣的係數。
第二行包含$N$個正整數$d_i$,代表第$i$題的難度。

對於所有的測資,$K\leq N \leq 10^ 5, K\leq 20, R\leq 10^ {15}, d_i \leq 10^ 5, C \leq 10^ 5, NK\leq 5\times 10^ 5$。

子任務(測資)額外限制分數
1(0~1)$K=1$1
2(2~7)$K=2$7
3(8~15)$N \leq 800$15
4(8~28)$N \leq 3000$26
4(0~35)$NK \leq 2\times 10^ 5$24
5(0~50)無限制27

Output Format

輸出一個整數代表盩僰麌最少能宣稱自己只寫幾題,若盩僰麌就算不裝弱也不能達到自己想要的樂趣,輸出-1

Sample Input

Sample Input #1
10 2 56 4
10 1 2 3 1 1 2 10 1 1

Sample Input #2
3 1 5 3
1 2 3

Sample Output

Sample Output #1
6

Sample Output #2
-1

Hints

範例測資一中,盩僰麌在第一天刷編號$1~6$的題目,獲得樂趣$(4-1)\times 10+(4-2)\times 1 + (4 - 3)\times 2 + (4 - 4) \times 3 + (4 - 5)\times 1 + (4 - 6)\times 1 = 31$,第二天刷編號$7~10$的題目,獲得樂趣$(4 - 1)\times 2 + (4 - 2)\times 10 + (4 - 3)\times 1 + (4 - 4)\times 1 = 27$,總樂趣$31 + 27 = 58$,是最佳的方案。

範例測資二中,唯一一種可行的方法為在第一天刷編號$1~3$的題目獲得總樂趣$4$,不能達到自己設的目標。

Problem Source

Problem Set by wayntuinfor

Subtasks

No. Testdata Range Score
1 0~1 1
2 2~7 7
3 8~15 15
4 8~28 26
5 0~35 24
6 0~50 27

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 5 6
1 1000 65536 262144 1 5 6
2 1000 65536 262144 2 5 6
3 1000 65536 262144 2 5 6
4 1000 65536 262144 2 5 6
5 1000 65536 262144 2 5 6
6 1000 65536 262144 2 5 6
7 1000 65536 262144 2 5 6
8 1000 65536 262144 3 4 5 6
9 1000 65536 262144 3 4 5 6
10 1000 65536 262144 3 4 5 6
11 1000 65536 262144 3 4 5 6
12 1000 65536 262144 3 4 5 6
13 1000 65536 262144 3 4 5 6
14 1000 65536 262144 3 4 5 6
15 1000 65536 262144 3 4 5 6
16 2000 65536 262144 4 5 6
17 2000 65536 262144 4 5 6
18 2000 65536 262144 4 5 6
19 2000 65536 262144 4 5 6
20 2000 65536 262144 4 5 6
21 2000 65536 262144 4 5 6
22 2000 65536 262144 4 5 6
23 2000 65536 262144 4 5 6
24 2000 65536 262144 4 5 6
25 2000 65536 262144 4 5 6
26 2000 65536 262144 4 5 6
27 2000 65536 262144 4 5 6
28 2000 65536 262144 4 5 6
29 1000 65536 262144 5 6
30 1000 65536 262144 5 6
31 1000 65536 262144 5 6
32 1000 65536 262144 5 6
33 1000 65536 262144 5 6
34 1000 65536 262144 5 6
35 1000 65536 262144 5 6
36 1000 65536 262144 6
37 1000 65536 262144 6
38 1000 65536 262144 6
39 1000 65536 262144 6
40 1000 65536 262144 6
41 1000 65536 262144 6
42 1000 65536 262144 6
43 1000 65536 262144 6
44 1000 65536 262144 6
45 1000 65536 262144 6
46 1000 65536 262144 6
47 1000 65536 262144 6
48 1000 65536 262144 6
49 1000 65536 262144 6
50 1000 65536 262144 6