Trong đêm trung thu, anh của bé Thu là người phụ trách chuẩn bị các phần quà cho các bạn nhỏ trong xóm. Mỗi phần quà đều có những chiếc bánh trung thu vô cùng hấp dẫn, đa dạng các hương liệu khác nhau từ đậu xanh, đậu đỏ đến khoai môn, trứng muối,... Cụ thể, dự kiến các hộp bánh trung thu sẽ gồm \(n\) loại vị khác nhau, được đánh số từ \(1\) đến \(n\). Máy làm bánh sẽ mất \(a_i\) phút để tạo ra loại bánh thứ \(i\).

Điểm đặc biệt ở chiếc máy là nó sẽ lần lượt hoàn thành các loại bánh theo vòng tròn, tức là với mỗi \(1 \leq i < n\), sau khi sản xuất xong loại bánh thứ \(i\) thì tiếp theo máy chỉ có thể làm ra loại bánh thứ \(i+1\). Khi máy làm xong hộp bánh thứ \(n\) thì nó chỉ có thể tạo ra bánh loại \(1\).

Anh của Thu chỉ có quỹ thời gian \(T\) phút để có thể tạo ra nhiều hộp bánh nhất có thể để tặng cho các bạn nhỏ, nhưng không tính toán được số hộp bánh nhiều nhất là bao nhiêu. Các bạn hãy giúp anh của Thu nhé.

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n\) và \(T\) (\(n \leq 10^5\), \(T \leq 10^{12}\))
• Dòng thứ hai chứa dãy số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \leq 10^4\))

Output

• Gồm một dòng duy nhất chứa kết quả của bài toán

Example

3 9
2 3 1

4

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(T \leq \sum{a_i}\)
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.