CSES 1159 ↗

Book Shop II

Maximum total pages buying at most `k i` copies of each book within budget `x`.

0
submissions
—
best score

You are in a book shop which sells n different books. You know the price, the number of pages and the number of copies of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy several copies of the same book.

Input

The first input line contains two integers n and x: the number of book and the maximum total price.

The next line contains n integers h1,h2,…,hn: the price of each book.

The next line contains n integers s1,s2,…,sn: the number of pages of each book.

The last line contains n integers k1,k2,…,kn: the number of copies of each book.

Output

Print one integer: the maximum number of pages.

Constraints

  • 1≤n≤100
  • 1≤x≤105
  • 1≤hi,si,ki≤1000

Example

Input:

3 10
2 6 3
8 5 4
3 5 2

Output:

28

Explanation: You can buy three copies of book 1 and one copy of book 3. The price is 3⋅2+3=9 and the number of pages is 3⋅8+4=28.

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/BookShopII/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.