{"raw_statement":[{"iden":"problem statement","content":"A monster with health $H$ has appeared right in front of you. Your magic power is now $0$.\nYou can use $N$ moves called move $1$, move $2$, $\\ldots$, move $N$, any number of times in any order.\nFor each $i = 1, 2, \\ldots, N$, move $i$ can only be used when your magic power is at least $C_i$, and its use will decrease your magic power by $C_i$ and the monster's health by $D_i$. Here, if $C_i$ is negative, decreasing your magic power by $C_i$ means increasing it by $-C_i$.\nFind the minimum possible number of times you use moves before the monster's health is $0$ or lower. The constraints of this problem guarantee that a finite number of uses of moves can make it $0$ or lower (see below)."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 300$\n*   $1 \\leq H \\leq 10^{18}$\n*   $-300 \\leq C_i \\leq 300$\n*   $C_i \\leq 0$ for some $1 \\leq i \\leq N$.\n*   $1 \\leq D_i \\leq 10^9$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $H$\n$C_1$ $D_1$\n$C_2$ $D_2$\n$\\vdots$\n$C_N$ $D_N$"},{"iden":"sample input 1","content":"3 48\n3 20\n-4 2\n1 5"},{"iden":"sample output 1","content":"5\n\nFrom the initial state where your magic power is $0$ and the monster's health is $48$, consider using moves as follows.\n\n*   Use move $2$. Now, your magic power is $4$, and the monster's health is $46$.\n*   Use move $3$. Now, your magic power is $3$, and the monster's health is $41$.\n*   Use move $1$. Now, your magic power is $0$, and the monster's health is $21$.\n*   Use move $2$. Now, your magic power is $4$, and the monster's health is $19$.\n*   Use move $1$. Now, your magic power is $1$, and the monster's health is $-1$.\n\nHere, you use moves five times before the monster's health is not greater than $0$, which is the minimum possible number."},{"iden":"sample input 2","content":"20 583988303060450752\n-64 273760634\n-238 960719353\n-114 191410838\n-250 357733867\n232 304621362\n-286 644706927\n210 37849132\n-230 556412112\n-142 136397527\n101 380675202\n-140 152300688\n190 442931589\n-187 940659077\n-12 312523039\n32 126515475\n-143 979861204\n105 488280613\n240 664922712\n290 732741849\n69 541282303"},{"iden":"sample output 2","content":"595990842"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}