Trong một thị trường chứng khoán, có một loại sản phẩm với số lượng cổ phiếu vô hạn. Giá cổ phiếu được cho trong \(N\) ngày, trong đó \(a_i\) là giá của một cổ phiếu vào ngày thứ \(i\). Có một quy định rằng vào ngày thứ \(i\), khách hàng chỉ có thể mua tối đa \(i\) cổ phiếu. Nếu khách hàng ban đầu có số tiền là \(k\), hãy tìm số lượng cổ phiếu tối đa mà khách hàng đó có thể mua được.

Ví dụ: Với \(N = 3\) ngày và giá cổ phiếu lần lượt là \(7, 10, 4\). Bạn có thể mua tối đa \(1\) cổ phiếu giá \(7\) vào ngày 1, tối đa \(2\) cổ phiếu giá \(10\) vào ngày 2 và tối đa \(3\) cổ phiếu giá \(4\) vào ngày 3.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) là số ngày.
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i\) là giá cổ phiếu ngày thứ \(i\)).
• Dòng thứ ba chứa số nguyên dương \(k\) là số tiền ban đầu của khách hàng.

Output

• Một số nguyên duy nhất là số lượng cổ phiếu tối đa có thể mua được.

Constraints

• \(1 \le N \le 10^5\)
• \(1 \le a_i \le 10^6\)
• \(1 \le k \le 10^{12}\)

Example

3
10 7 19
45

4

3
7 10 4
100

6