Đếm các cặp số Cho ba số nguyên dương n, A và B (1 ≤ n, A, B ≤ 2 × 10⁶).

Yêu cầu: Đếm số lượng cặp số (x, y) thỏa mãn điều kiện:

• 1 ≤ x < y ≤ n
• A ≤ x + y ≤ B

Dữ liệu vào: Từ file văn bản CAULI.INP ghi lần lượt các số là n, A và B.

Kết quả: Ghi ra file văn bản CAULI.OUT một số duy nhất là số lượng cặp số tìm được.

Ví dụ:

Giới hạn

• 70% test có ~ n \leq 2000 ~.
• 20% test có ~ 2000 < n \leq 10^5 ~ và ~ A = B ~.
• 10% test có ~ 1 \leq n, A, B \leq 2 \times 10^6 ~ và thỏa mãn ~ 1 \leq x < y \leq n, A \leq x + y \leq B ~.

Bài toán: Tối đa hóa số trang sách

Đề bài

Bạn ở một cửa hàng sách bán ~ n ~ loại sách khác nhau. Bạn biết giá và số trang của mỗi cuốn sách.

Bạn đã quyết định rằng tổng chi phí của các cuốn sách bạn mua sẽ không vượt quá ~ x ~. Hãy xác định số lượng trang tối đa mà bạn có thể mua, với điều kiện mỗi cuốn sách chỉ được mua một lần.

Input

• Dòng đầu tiên: hai số nguyên ~ n ~ và ~ x ~ (số sách và tổng chi phí tối đa).
• Dòng thứ hai: ~ n ~ số nguyên ~ h_1, h_2, \ldots, h_n ~ (giá của từng cuốn sách).
• Dòng thứ ba: ~ n ~ số nguyên ~ s_1, s_2, \ldots, s_n ~ (số trang của từng cuốn sách).

Output

• Một số nguyên: tổng số trang tối đa mà bạn có thể mua.

Ràng buộc

• ~ 1 \leq n \leq 1000 ~
• ~ 1 \leq x \leq 10^5 ~
• ~ 1 \leq h_i, s_i \leq 1000 ~

Ví dụ

Input:

4 10
4 8 5 3
5 12 8 1

Output:

13

Giải thích:

• Bạn có thể mua sách 1 và sách 3. Giá của chúng là ~ 4 + 5 = 9 ~, và tổng số trang là ~ 5 + 8 = 13 ~.