{"problem":{"name":"Foreign Exchange","description":{"content":"There are $N$ countries numbered $1$ to $N$. For each $i = 1, 2, \\ldots, N$, Takahashi has $A_i$ units of the currency of country $i$. Takahashi can repeat the following operation any number of times,","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc341_b"},"statements":[{"statement_type":"Markdown","content":"There are $N$ countries numbered $1$ to $N$. For each $i = 1, 2, \\ldots, N$, Takahashi has $A_i$ units of the currency of country $i$.\nTakahashi can repeat the following operation any number of times, possibly zero:\n\n*   First, choose an integer $i$ between $1$ and $N-1$, inclusive.\n*   Then, if Takahashi has at least $S_i$ units of the currency of country $i$, he performs the following action once:\n    *   Pay $S_i$ units of the currency of country $i$ and gain $T_i$ units of the currency of country $(i+1)$.\n\nPrint the maximum possible number of units of the currency of country $N$ that Takahashi could have in the end.\n\n## Constraints\n\n*   All input values are integers.\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq A_i \\leq 10^9$\n*   $1 \\leq T_i \\leq S_i \\leq 10^9$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$S_1$ $T_1$\n$S_2$ $T_2$\n$\\vdots$\n$S_{N-1}$ $T_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc341_b","tags":[],"sample_group":[["4\n5 7 0 3\n2 2\n4 3\n5 2","5\n\nIn the following explanation, let the sequence $A = (A_1, A_2, A_3, A_4)$ represent the numbers of units of the currencies of the countries Takahashi has. Initially, $A = (5, 7, 0, 3)$.\nConsider performing the operation four times as follows:\n\n*   Choose $i = 2$, pay four units of the currency of country $2$, and gain three units of the currency of country $3$. Now, $A = (5, 3, 3, 3)$.\n*   Choose $i = 1$, pay two units of the currency of country $1$, and gain two units of the currency of country $2$. Now, $A = (3, 5, 3, 3)$.\n*   Choose $i = 2$, pay four units of the currency of country $2$, and gain three units of the currency of country $3$. Now, $A = (3, 1, 6, 3)$.\n*   Choose $i = 3$, pay five units of the currency of country $3$, and gain two units of the currency of country $4$. Now, $A = (3, 1, 1, 5)$.\n\nAt this point, Takahashi has five units of the currency of country $4$, which is the maximum possible number."],["10\n32 6 46 9 37 8 33 14 31 5\n5 5\n3 1\n4 3\n2 2\n3 2\n3 2\n4 4\n3 3\n3 1","45"]],"created_at":"2026-03-03 11:01:14"}}