Bài toán: Tối thiểu số lần đi thang máy

Đề bài

Có $n$ người muốn lên tầng trên cùng của một tòa nhà, nơi chỉ có một thang máy. Bạn biết trọng lượng của mỗi người và trọng lượng tối đa $x$ mà thang máy có thể chở được trong một lần. Hãy xác định số lần đi thang máy ít nhất để đưa tất cả mọi người lên tầng trên cùng.

Input

• Dòng đầu tiên chứa hai số nguyên $n$ và $x$: số người và trọng lượng tối đa mà thang máy có thể chở trong một lần.
• Dòng thứ hai chứa $n$ số nguyên $w_1,w_2,\dots ,w_n$: trọng lượng của mỗi người.

Output

• In ra một số nguyên: số lần đi thang máy ít nhất.

Ràng buộc

• $1\le n\le 20$
• $1\le x\le {10}^9$
• $1\le w_i\le x$

Ví dụ

Input:

4 10
4 8 6 1

Output:

2

Giải thích:

• Thang máy có thể chở tối đa 10 kg.
• Chuyến thứ nhất: chở người có trọng lượng $4+6=10$ kg.
• Chuyến thứ hai: chở người có trọng lượng $8+1=9$ kg.
• Tổng cộng là 2 chuyến.