CSES - Book Shop

View as PDF
All submissions
Best submissions
Authors:
Flower_On_Stone , kitsune , Elektrikar
Problem type
Points: 1400 Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

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\) và \(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\) và \(3\). Giá của chúng là \(4 + 5 = 9\) và số lượng trang là \(5 + 8 = 13\).

Comments