CSES - Book Shop | Hiệu sách

Xem PDF

Điểm: 1400 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn đang ở trong một hiệu sách bán \(n\) cuốn 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 tổng số tiền mua sách của bạn tối đa là \(x\). Tổng số trang tối đa bạn có thể mua là bao nhiêu? Bạn chỉ có thể mua mỗi cuốn sách nhiều nhất một lần.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\)\(x\): số lượng sách và tổng số tiền tối đa.
  • Dòng tiếp theo chứa \(n\) số nguyên \(h_1,h_2,\ldots, h_n\): giá cả của mỗi cuốn sách.
  • Dòng cuối cùng chứa \(n\) số nguyên \(s_1,s_2,\ldots, s_n\): số trang của mỗi cuốn sách.

Output

  • In một số nguyên duy nhất: tổng số trang tối đa.

Constraints

  • \(1 \le n \le 1000\)
  • \(1 \le x \le 10^5\)
  • \(1 \le h_i,s_i \le 1000\)

Example

Sample input

4 10
4 8 5 3
5 12 8 1

Sample output
13

Note

Bạn có thể mua các cuốn sách \(1\)\(3\). Giá của chúng là \(4 + 5 = 9\) và số lượng trang là \(5 + 8 = 13\).


Bình luận