{"problem":{"name":"Katana Thrower","description":{"content":"You are going out for a walk, when you suddenly encounter a monster. Fortunately, you have $N$ katana (swords), Katana $1$, Katana $2$, $…$, Katana $N$, and can perform the following two kinds of atta","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc085_d"},"statements":[{"statement_type":"Markdown","content":"You are going out for a walk, when you suddenly encounter a monster. Fortunately, you have $N$ katana (swords), Katana $1$, Katana $2$, $…$, Katana $N$, and can perform the following two kinds of attacks in any order:\n\n*   Wield one of the katana you have. When you wield Katana $i$ $(1 ≤ i ≤ N)$, the monster receives $a_i$ points of damage. The same katana can be wielded any number of times.\n*   Throw one of the katana you have. When you throw Katana $i$ $(1 ≤ i ≤ N)$ at the monster, it receives $b_i$ points of damage, and you lose the katana. That is, you can no longer wield or throw that katana.\n\nThe monster will vanish when the total damage it has received is $H$ points or more. At least how many attacks do you need in order to vanish it in total?\n\n## Constraints\n\n*   $1 ≤ N ≤ 10^5$\n*   $1 ≤ H ≤ 10^9$\n*   $1 ≤ a_i ≤ b_i ≤ 10^9$\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $H$\n$a_1$ $b_1$\n$:$\n$a_N$ $b_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc085_d","tags":[],"sample_group":[["1 10\n3 5","3\n\nYou have one katana. Wielding it deals $3$ points of damage, and throwing it deals $5$ points of damage. By wielding it twice and then throwing it, you will deal $3 + 3 + 5 = 11$ points of damage in a total of three attacks, vanishing the monster."],["2 10\n3 5\n2 6","2\n\nIn addition to the katana above, you also have another katana. Wielding it deals $2$ points of damage, and throwing it deals $6$ points of damage. By throwing both katana, you will deal $5 + 6 = 11$ points of damage in two attacks, vanishing the monster."],["4 1000000000\n1 1\n1 10000000\n1 30000000\n1 99999999","860000004"],["5 500\n35 44\n28 83\n46 62\n31 79\n40 43","9"]],"created_at":"2026-03-03 11:01:14"}}