Sau khi mã hóa tin nhắn từ bài tập trước, Koruto điếng người khi nhận ra người mà anh yêu bấy lâu nay đã quyết định buông bỏ. Mặc dù chưa biết lý do thật sự là gì nhưng anh nghe phong phanh từ những người bạn rằng là "do mầy cọc tính quá", "do nó không thích mầy đâu", "nó lừa mầy thôi", "..." Không muốn tin vào sự thật phũ phàng, anh quyết định chọn cách trốn tránh, nhưng rồi nhận ra bản thân cần phải thay đổi rồi.

Để giúp Koruto vực lại tinh thần, Tiến sĩ Đá Orochimaru đã tạo ra 1 phần mềm giúp anh rèn luyện tinh thần. Cụ thể, trong phần mềm này, Koruto sẽ được hẹn hò với \(n\) cô gái (đương nhiên là bot thôi) và mỗi cô gái sẽ có mức độ thương tổn là \(a_i\) \((1 \le i \le n)\). Để quá trình luyện tập hiệu quả, mỗi lần Koruto sẽ làm quen với 1 cô gái và bị đá, nhận lại mức thương tổn và hồi phục để sẵn sàng bị cô gái tiếp theo đá tới khi hết bot mà thôi.

Quy tắc huấn luyện:

1. Thứ tự: Koruto có thể chọn gặp các cô gái theo bất kỳ thứ tự nào, miễn là phải trải qua đủ \(n\) mối tình.
2. Điều kiện: Anh chỉ có thể gặp một cô gái nếu chỉ số chịu đựng hiện tại lớn hơn mức thương tổn \(a_i\) của cô gái đó. Sau khi bị đá, chỉ số chịu đựng của anh sẽ giảm đi một lượng đúng bằng \(a_i\).
3. Trong một ngày: Koruto có thể bị đá bởi nhiều cô gái liên tiếp nếu chỉ số chịu đựng còn đủ.
4. Hồi phục: Nếu không đủ chỉ số chịu đựng để gặp cô gái tiếp theo, anh phải nghỉ ngơi để sang ngày hôm sau.
   • Ngày 1: Koruto bắt đầu với chỉ số chịu đựng bằng \(m\).
   • Từ Ngày 2 trở đi: Mỗi ngày mới bắt đầu, anh được cộng thêm \(k\) vào chỉ số chịu đựng hiện có (năng lượng dư từ ngày hôm trước được bảo lưu và cộng dồn với \(k\)).

Yêu cầu: Hãy giúp Tiến sĩ Đá Orochimaru tính toán số ngày tối thiểu để Koruto hoàn thành khóa huấn luyện (vượt qua tất cả \(n\) mối tình với các cô gái ảo).

Input

• Gồm 2 dòng
• Dòng đầu chứa số nguyên \(n, m, k\) \((1 \le n \le 10^5, 1 \le m, k \le 10^9)\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((a_i \le 10^6)\) là mức độ thương tổn của \(n\) cô gái

Output

• Gồm một dòng là số ngày tối thiểu.

Example

3 10 5
7 8 9

4

Scoring

• Subtask 1 (\(30\%\) điểm): \(n \le 10, m, k, a_i \le 100\).
• Subtask 2 (\(40\%\) điểm): \(n \le 10^3, m, k, a_i \le 10^6\).
• Subtask 3 (\(30\%\) điểm): Không có ràng buộc gì thêm (\(n \le 10^5, m, k \le 10^9, a_i \le 10^6\)).