Đóng thùng

Reimu có \(n\) món đồ cũ, nên cô định cho hết chúng vào hộp.

Món đồ thứ \(i\) nặng \(w_i\). Biết rằng mỗi hộp chỉ chịu được cân nặng là \(W\), hỏi số lượng thùng ít nhất Reimu phải dùng là bao nhiêu?

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(W\) (\(1 \le n \le 20\), \(1 \le W \le 10^9\)).

• Dòng thứ hai gồm \(n\) số nguyên \(w_1, w_2, \ldots, w_n\) (\(1 \le w_i \le W\)).

Output

In ra một số nguyên duy nhất là số thùng ít nhất Reimu cần dùng.

Example

Input:

4 5
1 2 3 4

Output:

2