Chuyến Thang Máy · canuc80k1502 · Thuật toán Canuc80k

Có $N$ người cần đi thang máy. Người thứ $i$ nặng $w_{i}$ , còn thang máy chở được tối đa $X$ đơn vị cân nặng trong một lượt.

Mỗi người phải tham gia đúng một lượt. Một lượt có thể chở bất kỳ nhóm người nào miễn tổng cân nặng của nhóm không vượt quá $X$ .

Hãy tìm số lượt ít nhất để đưa tất cả mọi người đi.

Input

Dòng đầu chứa hai số nguyên $N, X$ .
Dòng thứ hai chứa $N$ số nguyên $w_{1}, w_{2}, \dots, w_{N}$ .

Output

In số lượt thang máy nhỏ nhất cần dùng.

Constraints

$1 \leq N \leq 20$ .
$1 \leq X \leq 1 0^{9}$ .
$1 \leq w_{i} \leq X$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 10$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

5 10
2 3 5 6 4

Output

Giải thích: Có thể xếp ba người nặng $2, 3, 5$ vào một lượt và hai người nặng $6, 4$ vào lượt còn lại. Mỗi lượt đều đạt đúng sức chứa $10$ nên hai lượt là đủ.

Ý tưởng: Với mỗi tập người mask, lưu cặp dp[mask] = (rides, load): số lượt ít nhất và, trong số các cách dùng số lượt đó, tải nhỏ nhất của lượt cuối. So sánh các cặp theo thứ tự từ điển.
Ý tưởng: Khởi tạo dp[0]=(1,0). Để tính mask, thử chọn người i là người được thêm cuối cùng từ mặt nạ thu được khi bỏ i khỏi mask. Nếu tải lượt cuối cộng w_i không vượt X, đặt người đó vào lượt cuối; ngược lại tăng số lượt và bắt đầu lượt mới với tải w_i.
Ý tưởng: Chứng minh đúng. Trong một cách xếp tối ưu của mask, bỏ người được thêm cuối cùng cho một cách xếp hợp lệ của tập nhỏ hơn. Theo quy nạp, DP giữ cặp tốt nhất của tập đó. Quy tắc thêm người phản ánh chính xác hai khả năng: vào lượt cuối hoặc mở lượt mới. Khi số lượt bằng nhau, tải lượt cuối nhỏ hơn không bao giờ bất lợi cho người được thêm sau, nên thứ tự từ điển giữ đủ thông tin tối ưu.
Ý tưởng: Độ phức tạp. O(N·2^N) thời gian và O(2^N) bộ nhớ.