Làm bánh vòng tối đa (Bitter Alchemy)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ loại bánh vòng. Để làm một chiếc loại $i$ cần $m_i$ gam nguyên liệu. Bạn có $X$ gam nguyên liệu và bắt buộc làm ít nhất một chiếc của mỗi loại. Hãy tính số bánh vòng lớn nhất có thể làm.

Input

Dòng đầu chứa hai số nguyên $N, X$. $N$ dòng tiếp theo, dòng thứ $i$ chứa $m_i$.

Output

In một số nguyên: số bánh vòng lớn nhất có thể làm.

Subtask

Các giới hạn chung:

• $2 \le N \le 100$.

• $1 \le m_i \le 1000$.

• $\sum m_i \le X \le 10^5$.

• Subtask 1 (20 điểm): $N \le 10$, $X \le 1000$

• Subtask 2 (30 điểm): $N \le 50$, $X \le 10^4$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

3 1000
120
100
140

Output

9

Giải thích

Làm mỗi loại một chiếc tốn $360$ gam, còn $640$ gam. Loại rẻ nhất tốn $100$ gam nên làm thêm được $6$ chiếc. Tổng cộng $3+6=9$.