{"problem":{"name":"Friends and Travel costs","description":{"content":"There are $10^{100}+1$ villages, labeled with numbers $0$, $1$, $\\ldots$, $10^{100}$.   For every integer $i$ between $0$ and $10^{100}-1$ (inclusive), you can pay $1$ yen (the currency) in Village $i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc203_c"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $B_1$\n$:$\n$A_N$ $B_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc203_c","tags":[],"sample_group":[["2 3\n2 1\n5 10","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$."],["5 1000000000\n1 1000000000\n2 1000000000\n3 1000000000\n4 1000000000\n5 1000000000","6000000000\n\nNote that the answer may not fit into a $32$\\-bit integer."],["3 2\n5 5\n2 1\n2 2","10\n\nHe may have multiple friends in the same village."]],"created_at":"2026-03-03 11:01:14"}}