Trong một cuộc bầu cử, có \(N\) đảng và tổng cộng \(V\) phiếu. Hiện tại đã kiểm được một phần phiếu, mỗi đảng \(i\) có \(a_i\) phiếu và tổng không vượt quá \(V\). Số phiếu còn lại là \(V - \sum a_i\).

Bạn chọn một đảng \(X\) và có quyền phân phối toàn bộ số phiếu còn lại cho các đảng bất kỳ, có thể dồn hết cho một đảng hoặc chia nhỏ.

Sau khi phân phối, gọi \(b_i\) là số phiếu cuối cùng của đảng \(i\) và \(s_i\) là số ghế đảng \(i\) đã nhận được tại thời điểm đang xét. Ban đầu mọi \(s_i = 0\).

\(M\) ghế được chia theo phương pháp D'Hondt với ngưỡng \(5\%\):

• Loại các đảng có \(b_i\) nhỏ hơn \(5\%\) của tổng \(V\).
• Sau đó lặp \(M\) lần, mỗi lần chọn đảng còn lại có giá trị \(Q_i = \frac{b_i}{s_i + 1}\) lớn nhất để nhận ghế.
• Sau khi đảng \(i\) nhận một ghế, tăng \(s_i\) lên \(1\).
• Nếu hòa thì chọn đảng có chỉ số nhỏ hơn.

Hãy xác định số ghế lớn nhất mà đảng \(X\) có thể đạt được nếu phân phối số phiếu còn lại một cách tối ưu.

Input

• Dòng đầu tiên gồm bốn số nguyên \(V, N, M, X\).
• Dòng thứ hai gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

• In ra một số nguyên duy nhất là số ghế lớn nhất mà đảng \(X\) có thể đạt được.

Constraints

• \(1 \le N \le 2 \cdot 10^5\)
• \(1 \le M \le 2 \cdot 10^5\)
• \(1 \le V \le 10^{12}\)
• \(1 \le X \le N\)
• \(0 \le a_i \le V\)
• \(\sum a_i \le V\)

Example

20 4 5 1
4 3 6 1

3

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(N \le 8\), \(M \le 20\), \(V - \sum a_i \le 15\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 100\), \(M \le 200\).
• Subtask \(3\) (\(20\%\) số điểm): \(N \le 1000\), \(M \le 2000\), \(\sum a_i = V\).
• Subtask \(4\) (\(20\%\) số điểm): \(N \le 1000\), \(M \le 2000\).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc bổ sung.