活动中有 $N$ 种积分，编号为 $1$ 到 $N$。小泽最初拥有第 $i$ 种积分 $A_i$ 个。对于每个 $i=1,2,\ldots,N-1$，他可以重复执行兑换：支付 $S_i$ 个第 $i$ 种积分，获得 $T_i$ 个第 $i+1$ 种积分。

兑换只能从较小编号流向下一个编号。请计算通过最优兑换后，第 $N$ 种积分最多能有多少个。

输入格式

第一行包含整数 $N$。第二行包含 $N$ 个整数 $A_i$。接下来 $N-1$ 行，第 $i$ 行包含整数 $S_i,T_i$。

输出格式

输出第 $N$ 种积分的最大数量。

4
5 7 0 3
2 2
4 3
5 2

5

2
10 0
3 2

6

3
0 0 9
1 1
1 1

9

数据范围

• $2\le N\le2\timesimes10^5$
• $0\le A_i\le10^9$
• $1\le T_i\le S_i\le10^9$