ストーリー

「市場は開かれた！　すべて無（かみ）に返そう！」

問題文

市場では $N$ 種類のカードが売られており、種類 $i$ のカードは価格が $C_i$, 在庫が $S_i$ 枚です。

虹さんは、はじめ資金を $B$ だけもっており、これら合計 $\displaystyle \sum S_i$ 枚のカードからいくつか選んで購入します。ここで、価格が $c$ のカードを購入すると資金は $c$ だけ減少し、種類 $i$ のカードは最大 $S_i$ 枚までしか購入できません。また、購入後に資金が負になるような購入もできません。

市場の神である虹さんは市場操作により、整数 $k\ (1\leq k\leq N)$ をひとつ選んで、種類 $k$ のカードの価格を好きな正整数値に改変することができます。ただし、市場操作は高々 $1$ 回しか行うことができません。

虹さんは最大で合計何枚のカードを購入することができますか？

入力

$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$
• 入力はすべて整数

出力

虹さんが購入できるカードの枚数の最大値を一行に出力してください。

最後に改行してください。

部分点

各制約を満たすサブタスクに正解した場合、部分点が与えられます。

• サブタスク1: (30%)
• $N\leq 2000$
• $B\leq 10^5$
• $C_i\leq 1000$
• $S_i\leq 1000$
• サブタスク2: (70%)
• 追加の制約はない

サンプル

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