Description

A 子是一位經驗老到的實況主，面對來自網路上的攻擊與誹謗，他早有所準備，將自己化為多個身份，形成一人包圍網搭配最強律師使用法律鐵拳合力對抗敵人們。

A 子一共有 $N$ 個不同的身份，其中第 $i$ 個身份有著強度 $s_i$。最近他感到分身乏術，雖然發起攻擊才能對敵人造成傷害，但防禦來自敵人的攻擊，降低炎上的機會也是相當重要的。A 子認為他的弱點便是目前強度最低的身份，他決定透過吸收 $M$ 隻貓咪的靈魂來增強自己的弱點。每吸收一隻貓咪的靈魂，他便能增強目前的弱點，將該身份的強度增加 $C$。如果有多個強度 $s_i$ 最低的身份，他會選擇最前面的身份加強，也就是 $i$ 最小的一個。

A 子做事從不馬虎，必先縝密規劃，在準備好之前絕不走漏風聲。他想先知道，在吸收 $M$ 隻貓咪的靈魂後，其弱點的強度會是多少？

Input Format

輸入的第一行包含三個正整數 $N,M,C$，表示身份的數量、貓咪的數量、每隻貓咪的靈魂能提供的強度。第二行包含 $N$ 個正整數 $s_i$，表示一開始每個身份的強度。

$1 \le N \le 3 \times 10^ 5$
$1 \le M \le 10^ 9$
$1 \le C \le 10^ 9$
$1 \le s_i \le 10^ 9$

Output Format

輸出一個整數，表示吸收 $M$ 隻貓咪的靈魂後，其弱點的強度會是多少。

Sample Input 1

5 4 3
3 1 4 1 5

Sample Output 1

Hints

Problem Source

Subtasks

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	1~7	$s_1 = s_2 = \ldots = s_N$	4
3	8~16	$1 \le N \le 3000$ 且 $1 \le M \le 3000$	7
4	8~29	$1 \le N \le 3000$	24
5	8~16, 30~42	$1 \le M \le 3000$	10
6	43~55	$C=1$	23
7	0~85	無額外限制	32

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	1048576	65536	1 7
1	1000	1048576	65536	2 7
2	1000	1048576	65536	2 7
3	1000	1048576	65536	2 7
4	1000	1048576	65536	2 7
5	1000	1048576	65536	2 7
6	1000	1048576	65536	2 7
7	1000	1048576	65536	2 7
8	1000	1048576	65536	3 4 5 7
9	1000	1048576	65536	3 4 5 7
10	1000	1048576	65536	3 4 5 7
11	1000	1048576	65536	3 4 5 7
12	1000	1048576	65536	3 4 5 7
13	1000	1048576	65536	3 4 5 7
14	1000	1048576	65536	3 4 5 7
15	1000	1048576	65536	3 4 5 7
16	1000	1048576	65536	3 4 5 7
17	1000	1048576	65536	4 7
18	1000	1048576	65536	4 7
19	1000	1048576	65536	4 7
20	1000	1048576	65536	4 7
21	1000	1048576	65536	4 7
22	1000	1048576	65536	4 7
23	1000	1048576	65536	4 7
24	1000	1048576	65536	4 7
25	1000	1048576	65536	4 7
26	1000	1048576	65536	4 7
27	1000	1048576	65536	4 7
28	1000	1048576	65536	4 7
29	1000	1048576	65536	4 7
30	1000	1048576	65536	5 7
31	1000	1048576	65536	5 7
32	1000	1048576	65536	5 7
33	1000	1048576	65536	5 7
34	1000	1048576	65536	5 7
35	1000	1048576	65536	5 7
36	1000	1048576	65536	5 7
37	1000	1048576	65536	5 7
38	1000	1048576	65536	5 7
39	1000	1048576	65536	5 7
40	1000	1048576	65536	5 7
41	1000	1048576	65536	5 7
42	1000	1048576	65536	5 7
43	1000	1048576	65536	6 7
44	1000	1048576	65536	6 7
45	1000	1048576	65536	6 7
46	1000	1048576	65536	6 7
47	1000	1048576	65536	6 7
48	1000	1048576	65536	6 7
49	1000	1048576	65536	6 7
50	1000	1048576	65536	6 7
51	1000	1048576	65536	6 7
52	1000	1048576	65536	6 7
53	1000	1048576	65536	6 7
54	1000	1048576	65536	6 7
55	1000	1048576	65536	6 7
56	1000	1048576	65536	7
57	1000	1048576	65536	7
58	1000	1048576	65536	7
59	1000	1048576	65536	7
60	1000	1048576	65536	7
61	1000	1048576	65536	7
62	1000	1048576	65536	7
63	1000	1048576	65536	7
64	1000	1048576	65536	7
65	1000	1048576	65536	7
66	1000	1048576	65536	7
67	1000	1048576	65536	7
68	1000	1048576	65536	7
69	1000	1048576	65536	7
70	1000	1048576	65536	7
71	1000	1048576	65536	7
72	1000	1048576	65536	7
73	1000	1048576	65536	7
74	1000	1048576	65536	7
75	1000	1048576	65536	7
76	1000	1048576	65536	7
77	1000	1048576	65536	7
78	1000	1048576	65536	7
79	1000	1048576	65536	7
80	1000	1048576	65536	7
81	1000	1048576	65536	7
82	1000	1048576	65536	7
83	1000	1048576	65536	7
84	1000	1048576	65536	7
85	1000	1048576	65536	7

Submit out of contest

919 . 我獨自升級