Hôm nay Hoa quyết định đi chợ mua hoa quả giúp mẹ. Khu chợ tại nơi sinh sống của Hoa bao gồm \(n\) gian hàng được xếp thành một vòng tròn. Các gian hàng được đánh số từ \(1\) đến \(n\) theo chiều kim đồng hồ (gian hàng \(n\) nằm cạnh gian hàng \(1\)). Gian hàng thứ \(i\) (\(1 \leq i \leq n\)) bán một loại quả với giá \(a_i\) đồng. Giả sử rằng mỗi gian hàng có một nguồn cung cấp không giới hạn.

Hoa muốn dùng \(m\) đồng để mua hoa quả. Kế hoạch mua của Hoa là như sau:

• Đầu tiên, Hoa ghé thăm gian hàng \(1\).
• Hoa sẽ mua đúng một quả nếu còn đủ tiền.
• Sau đó, Hoa sẽ di chuyển qua gian hàng bên cạnh theo chiều kim đồng hồ và tiếp tục kế hoạch.

Vì số tiền của Hoa có giới hạn, kế hoạch sẽ dừng lại khi Hoa không còn đủ tiền để mua bất kỳ loại quả nào. Hãy tìm số lượng quả mà Hoa mua được.

Input

• Dòng đầu tiên chứa số nguyên \(n\) và \(m\) \((1 \leq n \leq 10^{5}, 1 \leq m \leq 10^{18})\) lần lượt là số lượng gian hàng và số tiền tối đa mà Hoa có thể dùng.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) là giá tiền của mỗi loại quả tại mỗi gian hàng.

Ouput

• In ra một số nguyên duy nhất là số lượng quả mà Hoa mua được.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n = 2\).
• Subtask \(2\) (\(30\%\) số điểm): \(a_{1} \leq a_{2} \leq \ldots \leq a_{n}\).
• Subtask \(3\) (\(30\%\) số điểm): \(m \leq \min(a_{1}, a_{2}, \ldots, a_{n}) \times 10^{6}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 38
5 2 5

10

5 21
2 4 100 2 6

6