1614. 请 规 范 训 练
时间限制：1000 MS 内存限制：128 MB
题目描述
## 题目描述 小火龙通过重重难关无意中取得魔法石后，寄居在桑叶教授体内的冥王与董美娃对话，逼迫他交出魔法石。桑叶教授为得到魔法石施展魔法，将哈利带到了一个神秘空间： 这个空间是一个正 $n$ 边形，有 $n$ 个顶点，桑叶教授给董美娃 $n$ 个令牌（令牌上有数字），保证每个令牌上的数不重复，要求董美娃将 $n$ 个令牌分别放在 $n$ 边形的 $n$ 个顶点上，现在桑叶教授让董美娃任选一个点作为起点，以这个点按顺时针绕空间一周，每经过一个顶点就将一个令牌放在这个顶点上，并计算，之前每个顶点上的令牌的数字和当前顶点上令牌的数字的差，并将差的和作为这个顶点的魔力值，绕 nn 边形一周回到起点时结束该过程（每个顶点只会获得一次魔力值，回到起点不会再累计魔力值，魔力值计算从第二个令牌开始）。令牌的放置方法不同，魔力值的总和（每个顶点的魔力值的和）显然不一样，当 $n$ 个令牌放置完毕后，董美娃将获得这个总魔力值，并消耗魔力值释放魔法，突破这个空间，董美娃掌握的魔法只有 kk 种 ，每种魔法消耗的魔力值分别为 $a_1,a_2,a_3 \cdots$，每种魔法可以释放$b_1,b_2,b_3 \cdots b_k$ 次，输出释放魔法的最大次数 ## 输入格式 输入一个数 $n$ 代表正多边形顶点数 ($3 \leq n \leq 10^5$)，输入一个数 kk 代表董美娃掌握的魔法种类 $(1 \leq k \leq 100)$ 接下来一行有 $n$ 个数 $a_i$ 代表令牌上得数 ($1\leq a_i \leq 10^9$，保证 $a_i$ 各不相同) 接下来 kk 行分别是 $a_i$和 $b_i$ ($0 \leq a_i,b_i \leq 100$) ## 输出格式 输出能够释放魔法得最大次数 ## 输入 ```in1 3 3 1 2 3 10 1 4 2 3 2 ``` ## 输出 ```out1 1 ``` ```in2 8 1 7 11 15 16 3 2 9 10 14 2 ``` ```out2 2 ``` ## 提示