Description

一家大型超市有 k 台收银台（1 ≤ k ≤ 5），第 i 台收银台的结账速度为 v[i]（每分钟可以处理的商品件数），v[i] ≥ 1。 超市在一天的营业时间里会陆续有 n 位顾客（1 ≤ n ≤ 200 000）进入。第 j 位顾客的信息为 t[j] – 到达超市的时间（单位：分钟，0 ≤ t[j] ≤ 10⁹）， p[j] – 需要结账的商品件数（1 ≤ p[j] ≤ 10⁴）。 t[1] ≤ t[2] ≤ … ≤ t[n]（到达时间非递减）。 当顾客到达时，他会立即选择一台收银台加入排队。 选择原则： 1.计算每台收银台 如果把该顾客放在队尾，顾客完成结账的时间 finish其中 free[i] 表示第 i 台收银台在当前时刻 已经没有顾客，即它可以在 free[i] 时刻开始为新顾客服务（如果 free[i] < t[j]，则收银台会空等到 t[j]）。 2. 顾客挑选 finish 最小 的收银台加入其队尾；如果出现多台 finish 相同的情况，取编号最小的那台。 加入队列后，该收银台的 free 时间立即更新为该顾客的 finish（因为顾客会在后面继续排队）。 任务：输出所有顾客全部结账完毕的时间（即所有 finish 的最大值）。 如果所有顾客在同一时刻结束结账，则答案就是该时刻的数值。

Format

Input

第 1 行：两个整数 k、n。 第 2 行：k 个整数 v[i]（每分钟处理的商品件数）。 接下来 n 行：每行两个整数 t[j]、p[j]，分别是第 j 位顾客的到达时间和商品件数。

Output

一行一个整数：所有顾客全部结账完毕的时间（单位：分钟）。

Samples

2 3 
2 3 
0 4 
1 2 
2 3

3

Limitation

顾客 到达时间 t 商品数 p 选择的收银台 开始结账 start 用时 work (= ⌈p / v⌉) 完成时间 finish 1 0 4 1（速度 2） max(0,0)=0 ⌈4/2⌉ = 2 0 + 2 = 2 2 1 2 2（速度 3） max(1,0)=1 ⌈2/3⌉ = 1 1 + 1 = 2 3 2 3 1（速度 3） max(2,2)=2 ⌈3/3⌉ = 1 2 + 1 = 3 顾客 1 把收银台 1 的 free 更新为 2，answer = 2。 顾客 2 把收银台 2 的 free 更新为 2，answer = max(2,2)=2。 顾客 3 看到收银台 1 在 2 时空闲，收银台 2 也在 2 时空闲。选择收银台1 计算得到 finish（2+1=3）： 此时所有顾客的完成时间分别为 2、2、3，最大值为 3。

【数据范围与约束】 项目 取值范围 k 1 ≤ k ≤ 5 n 1 ≤ n ≤ 200 000 v[i] 1 ≤ v[i] ≤ 10⁴ t[j] 0 ≤ t[j] ≤ 10⁹，且非递减 p[j] 1 ≤ p[j] ≤ 10⁴ 所有计算结果均不超过 10⁹（使用 64 位整数安全）