问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
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, possibly zero:

- First, choose an integer i between 1 and N-1, inclusive.
- Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
- Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).



Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Input

The input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

Output

Print the answer.

Constraints


- All input values are integers.
- 2 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 1 \leq T_i \leq S_i \leq 10^9

Sample Input 1

4
5 7 0 3
2 2
4 3
5 2

Sample Output 1

5

In 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).
Consider performing the operation four times as follows:

- 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).
- 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).
- 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).
- 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).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

45

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
A = list(map(int, data[1:N+1]))
S = []
T = []

for i in range(N-1):
S.append(int(data[N+1+2*i]))
T.append(int(data[N+1+2*i+1]))

for i in range(N-2, -1, -1):
if A[i] >= S[i]:
times = A[i] // S[i]
A[i] -= times * S[i]
A[i+1] += times * T[i]

print(A[-1])
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
deepseek-r1

```python
n = int(input())
A = list(map(int, input().split()))
exchanges = [tuple(map(int, input().split())) for _ in range(n-1)]

for i in range(n-1):
s, t = exchanges[i]
k = A[i] // s
A[i] -= k * s
A[i+1] += k * t

print(A[-1])
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading

def main():
import sys
sys.setrecursionlimit(1 << 25)
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
S = []
T = []
for _ in range(N - 1):
s_i, t_i = map(int, sys.stdin.readline().split())
S.append(s_i)
T.append(t_i)
total_A = A.copy()
for i in range(N - 1):
num = total_A[i] // S[i]
total_A[i] -= num * S[i]
total_A[i + 1] += num * T[i]
print(total_A[N - 1])

if __name__ == "__main__":
threading.Thread(target=main).start()
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
def max_currency_in_country_N():
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
A = list(map(int, data[1:N+1]))
S = []
T = []

index = N + 1
for i in range(N - 1):
S.append(int(data[index]))
T.append(int(data[index + 1]))
index += 2

# We will iterate from the last country to the first
# and calculate the maximum possible currency in each country
for i in range(N - 2, -1, -1):
# Calculate the maximum number of times we can perform the operation
max_operations = A[i] // S[i]
# Calculate the maximum currency we can transfer to the next country
max_transfer = max_operations * T[i]
# Update the currency in the next country
A[i + 1] += max_transfer
# Update the currency in the current country
A[i] -= max_operations * S[i]

# The result is the amount of currency in the last country
print(A[N - 1])

max_currency_in_country_N()
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE
def main():
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
A = list(map(int, data[1:N+1]))
operations = []
idx = N + 1
for i in range(N-1):
S_i = int(data[idx])
T_i = int(data[idx+1])
operations.append((S_i, T_i))
idx += 2

for i in range(N-1):
S_i, T_i = operations[i]
if A[i] >= S_i:
A[i+1] = min(A[i+1] + T_i, A[i] - S_i)

print(A[-1])

if __name__ == "__main__":
main()
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys

def solve():
n = int(input())
a = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(n-1)]

for i in range(n-2, -1, -1):
s, t = st[i]
k = a[i] // s
a[i] -= k * s
a[i+1] += k * t
if s <= t:
continue
else:
a[i+1] += max((a[i] + s - 1) // s - 1, 0) * (t - s)

print(a[-1])

if __name__ == "__main__":
solve()
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys

def solve():
n = int(input())
a = list(map(int, input().split()))
st = []
for _ in range(n - 1):
s, t = map(int, input().split())
st.append((s, t))

for i in range(n - 2, -1, -1):
s, t = st[i]
if a[i] >= s:
cnt = a[i] // s
a[i] %= s
a[i + 1] += min(cnt, (a[i + 1] + s - 1) // s) * t

print(a[-1])

if __name__ == "__main__":
solve()
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
N = int(input())
A = list(map(int, input().split()))
ST = [list(map(int, input().split())) for _ in range(N-1)]

for i in range(N-1, 0, -1):
s, t = ST[i-1]
q, r = divmod(A[i-1], s)
A[i-1] = r
A[i] += q * t

print(A[-1])
```
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
baichuan4 ```python
import sys

def read_input():
N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
ST = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N - 1)]
return N, A, ST

def max_units(N, A, ST):
dp = [0] * N
dp[0] = A[0]

for i in range(1, N):
dp[i] = A[i]
for j in range(i):
if dp[j] >= ST[j][0]:
dp[i] = max(dp[i], dp[j] - ST[j][0] + ST[j][1])

return dp[-1]

def main():
N, A, ST = read_input()
result = max_units(N, A, ST)
print(result)

if __name__ == "__main__":
main()
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
doubao ```python
N = int(input())
A = list(map(int, input().split()))
S = []
T = []
for _ in range(N - 1):
s, t = map(int, input().split())
S.append(s)
T.append(t)

dp = [0] * N
dp[0] = A[0]
for i in range(1, N):
for j in range(i):
if A[j] >= S[j]:
dp[i] = max(dp[i], dp[j] - S[j] + T[j])
dp[i] += A[i]

print(dp[N - 1])
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading

def main():
import sys
sys.setrecursionlimit(1 << 25)
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
S = []
T = []
for _ in range(N - 1):
s_i, t_i = map(int, sys.stdin.readline().split())
S.append(s_i)
T.append(t_i)
total_A = A.copy()
for i in range(N - 1):
num = total_A[i] // S[i]
total_A[i] -= num * S[i]
total_A[i + 1] += num * T[i]
print(total_A[N - 1])

if __name__ == "__main__":
threading.Thread(target=main).start()
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
kimi ```python
# YOUR CODE HERE
N = int(input())
A = list(map(int, input().split()))
ST = [list(map(int, input().split())) for _ in range(N - 1)]

dp = [0] * N
dp[0] = A[0]

for i in range(N - 1):
(s, t) = ST[i]
dp[i + 1] = max(dp[i + 1], dp[i])
dp[i + 1] = max(dp[i + 1], dp[i] + (A[i + 1] + dp[i] - 1) // s * t)

print(dp[-1])
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
minimax ```python
# YOUR CODE HERE
import sys

def max_currency(N, A, S, T):
# Initialize the maximum currency of country N to its initial value
max_A_N = A[-1]

# Start from the second last country and move towards the first country
for i in range(N - 2, -1, -1):
# Calculate the number of times Takahashi can perform the operation for country i
operations = A[i] // S[i]
# Update the currency of country i and country (i+1) after performing the operations
A[i] -= operations * S[i]
A[i + 1] += operations * T[i]
# Update the maximum currency of country N
max_A_N += operations * T[i]

return max_A_N

# Read the inputs from stdin
N = int(input())
A = list(map(int, input().split()))
S = []
T = []
for _ in range(N - 1):
s, t = map(int, input().split())
S.append(s)
T.append(t)

# Solve the problem and write the answer to stdout
print(max_currency(N, A, S, T))
 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
wenxinyiyan ```python
# Read the number of countries
N = int(input())

# Read the initial amounts of currencies
A = list(map(int, input().split()))

# Read the exchange rates
exchanges = [tuple(map(int, input().split())) for _ in range(N - 1)]

# Define a function to calculate the maximum amount of currency for country N
def max_currency(A, exchanges):
# Iterate over the exchanges from the last to the first
for i in range(N - 2, -1, -1):
S_i, T_i = exchanges[i]
# While we can exchange currency from country i to country (i+1)
while A[i] >= S_i:
# Calculate the number of exchanges we can perform
exchanges_count = A[i] // S_i
# Update the amount of currency for country i
A[i] -= exchanges_count * S_i
# Update the amount of currency for country (i+1)
A[i + 1] += exchanges_count * T_i
# Return the maximum amount of currency for country N
return A[-1]

# Calculate and print the maximum amount of currency for country N
print(max_currency(A, exchanges))
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
zhipu ```python
def main():
import sys
input = sys.stdin.read
data = input().split()

n = int(data[0])
a = list(map(int, data[1:n+1]))
st = []
index = n+1
for i in range(n-1):
s = int(data[index])
t = int(data[index+1])
st.append((s, t))
index += 2

# Process each country from 1 to N-1
for i in range(n-1):
s, t = st[i]
# Calculate the maximum number of operations we can perform
max_operations = a[i] // s
# Update the currency of country i+1
a[i+1] += max_operations * t
# Reduce the currency of country i after operations
a[i] -= max_operations * s

# The answer is the amount of currency in the last country
print(a[-1])

if __name__ == "__main__":
main()
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]
deepseek-v3 ```python
# YOUR CODE HERE
N = int(input())
A = list(map(int, input().split()))
S = []
T = []
for _ in range(N-1):
s, t = map(int, input().split())
S.append(s)
T.append(t)

for i in range(N-1):
if A[i] >= S[i]:
max_transfer = A[i] // S[i]
A[i] -= max_transfer * S[i]
A[i+1] += max_transfer * T[i]

print(A[-1])
```		 [{"input": "4\n5 7 0 3\n2 2\n4 3\n5 2\n", "output": "5\n", "testtype": "stdin"}, {"input": "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\n", "output": "45\n", "testtype": "stdin"}]