Story

"The market is open! Let us return everything to nothing (kami)!"

Problem Statement

The market sells $N$ types of cards. Cards of type $i$ have price $C_i$, and there are $S_i$ of them in stock.

Niji initially has funds of $B$ and buys some cards chosen from these $\displaystyle \sum S_i$ cards in total. Buying a card with price $c$ decreases the funds by $c$, and at most $S_i$ cards of type $i$ can be bought. A purchase that would make the funds negative is not allowed.

Niji, the god of the market, can use market manipulation to choose one integer $k\ (1\leq k\leq N)$ and change the price of cards of type $k$ to any positive integer value. However, market manipulation can be performed at most $1$ time.

What is the maximum total number of cards Niji can buy?

Input

$N$
$B$
$C_1\ C_2\ \cdots\ C_N$
$S_1\ S_2\ \cdots\ S_N$

• $1\leq N\leq 10^5$
• $1\leq B\leq 10^9$
• $1\leq C_i\leq 10^5$
• $1\leq S_i\leq 10^5$
• All inputs are integers.

Output

Print the maximum number of cards Niji can buy on one line.

Print a newline at the end.

Subtasks

Partial points are awarded for correctly solving a subtask that satisfies the respective constraints.

• Subtask 1: (30%)
• $N\leq 2000$
• $B\leq 10^5$
• $C_i\leq 1000$
• $S_i\leq 1000$
• Subtask 2: (70%)
• No additional constraints.

Sample

2
3
1 2
1 2

3

10
30
5 4 6 7 8 3 4 2 2 4
2 1 1 2 1 4 5 3 2 1

14