{"raw_statement":[{"iden":"problem statement","content":"There are $10^{100}+1$ villages, labeled with numbers $0$, $1$, $\\ldots$, $10^{100}$.  \nFor every integer $i$ between $0$ and $10^{100}-1$ (inclusive), you can pay $1$ yen (the currency) in Village $i$ to get to Village $(i + 1)$. There is no other way to travel between villages.\nTaro has $K$ yen and is in Village $0$ now. He will try to get to a village labeled with as large a number as possible.  \nHe has $N$ friends. The $i$\\-th friend, who is in Village $A_i$, will give Taro $B_i$ yen when he reaches Village $A_i$.  \nFind the number with which the last village he will reach is labeled."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq K \\leq 10^9$\n*   $1 \\leq A_i \\leq 10^{18}$\n*   $1 \\leq B_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $B_1$\n$:$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"2 3\n2 1\n5 10"},{"iden":"sample output 1","content":"4\n\nTakahashi will travel as follows:\n\n*   Go from Village $0$ to Village $1$, for $1$ yen. Now he has $2$ yen.\n*   Go from Village $1$ to Village $2$, for $1$ yen. Now he has $1$ yen.\n*   Get $1$ yen from the $1$\\-st friend in Village $2$. Now he has $2$ yen.\n*   Go from Village $2$ to Village $3$, for $1$ yen. Now he has $1$ yen.\n*   Go from Village $3$ to Village $4$, for $1$ yen. Now he has $0$ yen, and he has no friends in this village, so his journey ends here.\n\nThus, we should print $4$."},{"iden":"sample input 2","content":"5 1000000000\n1 1000000000\n2 1000000000\n3 1000000000\n4 1000000000\n5 1000000000"},{"iden":"sample output 2","content":"6000000000\n\nNote that the answer may not fit into a $32$\\-bit integer."},{"iden":"sample input 3","content":"3 2\n5 5\n2 1\n2 2"},{"iden":"sample output 3","content":"10\n\nHe may have multiple friends in the same village."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}