Ở thế giới song song, nqplant vs Zombie là một trò chơi điện tử phòng thủ do công ty NQStudio phát triển và phát hành. Mục tiêu của người chơi là ngăn không cho zombie của tiến sĩ uosbu tiếp cận ngôi nhà nqson đang ở. Trong chế độ cơ bản, người chơi trồng các loại thực vật khác nhau trên sân để ngăn chặn zombie tiến vào nhà.

Hôm nay kỷ niệm 21 năm ngày thành lập công ty NQStudio, nqplant vs Zombie ra mắt một chế độ chơi giải trí mới có nội dung như sau:

• Một màn chơi bây giờ chỉ còn một hàng với độ dài là n ô vuông
• Người chơi chỉ được phép chọn và trồng một nqplant duy nhất ở vị trí bất kỳ, con nqplant này luôn có thể tấn công được x con zombie ở đằng trước và gây sát thương y cho các con zombie đó (x do màn chơi quyết định và y do người chơi chọn)
• Game sẽ chỉ xuất hiện m con zombie, mỗi con zombie có một lượng hp \(a_i\) xếp theo thứ tự từ trái sang phải
• Mỗi lượt của trò chơi sẽ được diễn ra như sau:
  1. Tất cả các con zombie sẽ bước 1 bước
  2. Xuất hiện một con zombie ở vị trí tiếp theo
  3. Cây nqplant sẽ bắn x con zombie ờ đầu với sát thương là y, zombie sẽ chết nếu máu tụt xuống 0hp
• Sau khi cây nqplant bắn xong, nếu zombie chạm vào cây nqplant thì cây đó sẽ bị ăn mất và trò chơi sẽ thua. Chiến thắng khi tất cả các con zombie bị tiêu diệt.

Một màn chơi được minh họa như sau:

Màn chơi dài 5 ô, nqplant có thể bắn được 2 con ở đầu
Có 3 zombie xuất hiện theo thứ tự lần lượt có lượng hp là: 9 5 6

Ký hiệu: P là vị trí nqplant, số là máu của zombie, x là con zombie vừa chết
Giả sử người chơi chọn cây có sức mạnh 1, trò chơi sẽ chạy như sau:
        Trước khi nqplant bắn   |   Sau khi nqplant bắn
Bước 1:     P . . . 9           |       P . . . 8
Bước 2:     P . . 8 5           |       P . . 7 4
Bước 3:     P . 7 4 6           |       P . 6 3 6
Bước 4:     P 6 3 6 .           |       P 5 2 6 .
Bước 5:     P52 6 . .           |       4 1 6 . .
Kết quả zombie thắng

Giả sử người chơi chọn cây có sức mạnh 2, trò chơi sẽ chạy như sau:
        Trước khi nqplant bắn   |   Sau khi nqplant bắn
Bước 1:     P . . . 9           |       P . . . 7
Bước 2:     P . . 7 5           |       P . . 5 3
Bước 3:     P . 5 3 6           |       P . 3 1 6
Bước 4:     P 3 1 6 .           |       P 1 x 6 .
Bước 5:     P1. 6 . .           |       Px. 4 . .
Bước 6:     P 4 . . .           |       P 2 . . .
Bước 7:     P2. . . .           |       Px. . . .   (zombie vừa tiếp cận được nqplant thì chết)
Kết quả nqplant thắng

Bảng xếp hạng của trò chơi sẽ hiển thị những người chơi sử dụng con nqplant có ít sát thương nhất mà vẫn dành chiến thắng. Hãy tìm lượng sát thương đó.

Đầu vào

Dòng đầu tiên gồm 3 số tự nhiên \(n, m, x\) với n dại diện cho độ dài màn chơi, m số con zombie, x đại diện cho số lượng zombie mà nqplant có thể tấn công cùng lúc

Dòng tiếp theo gồm \(m\) số tự nhiên từ \(a_1,a_2,...,a_m\) biểu thị số máu từng con zombie

Đầu ra

Một dòng duy nhất là kết quả bài toán

Giới hạn

25%: \(n,m,x,a_i \le 100\)

25%: \(n,m,x \le 1000; a_i \le 10^9\)

50%: \(n,m,x \le 10^5; a_i \le 10^9\)

Ví dụ

Đầu vào

5 3 2
9 5 6

Đầu ra

2