D - You and Idol TSG
Ceylon
2
s
1024
MB
350
点
問題文
アイドルグループ Tokyo Sushi Girls (以下、 TSG) には $N$ 人のメンバーがいます。 TSG の大ファンであるあなたは、それぞれのメンバーの応援グッズを買って応援することにしました。メンバー $i\ (1 \leq i \leq N)$ の応援グッズは $C_i$ 円で、 $1$ 個買うごとにメンバー $i$ の嬉しさが $H_i$ 増加します。
あなたの所持金は $X$ 円です。TSG 箱推しのあなたは、なるべく平等になるようにグッズを買いたいと思っています。
メンバー $i$ のグッズを $x_i (\ge 0)$ 個買うとき、 $\sum_{i=1}^N C_i x_i \leq X$ が満たされる買い方の中で $ \min_{1\leq i\leq N} ( H_i x_i )$ の最大値を求めてください。
制約
- 入力は全て整数
- $1 \leq N \leq 2\times 10^5$
- $1 \leq X \leq 2\times 10^5$
- $1 \leq C_i \leq 10^4$
- $1 \leq H_i \leq 10^4$
入力
入力は以下の形式で標準入力から与えられる。
$N\ X$
$C_1\ C_2\ \ldots\ C_N$
$H_1\ H_2\ \ldots\ H_N$
出力
答えを 1 行に出力せよ。
入力例 1
4 1100
100 200 300 100
3 2 1 2
出力例 1
2
例えば、以下のような買い方が考えられます。
- メンバー 1 の応援グッズを 1 個買う。 100 円かかり、メンバー 1 の嬉しさが 3 増える。
- メンバー 2 の応援グッズを 1 個買う。 200 円かかり、メンバー 2 の嬉しさが 2 増える。
- メンバー 3 の応援グッズを 2 個買う。 600 円かかり、メンバー 3 の嬉しさが 2 増える。
- メンバー 4 の応援グッズを 1 個買う。 100 円かかり、メンバー 4 の嬉しさが 2 増える。
このとき、合計金額は 1000 円で、メンバーに与えられた嬉しさの最小値は 2 になります。全てのメンバーの嬉しさを 3 以上増やすような買い方は存在しないので、 2 を出力します。
入力例 2
10 100
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8
出力例 2
6