糖

题目描述 有� + 1 个城市在一条线上，从左往右从 0 开始标号。其中第�个城市距离城市 0 的距离为�� 。你要从 0 号城市开始出发，依次经过城市 1,2, …, � − 1 到达城市�。 你每经过一单位的距离需要吃一颗糖。每个城市有一个糖果店，有无限多的糖，第 �个城市的糖果店买一个糖果的价格是���� ，卖一个糖果的价格是����� ，你可以在 商店里出售多余的糖果。你最多能同时携带�单位糖果。

你想知道最少要多少钱能完成整个旅行。

输入格式 第一行两个整数�, �。

接下来一行�个整数�1 , �2 , …, �� ，保证��−1 < �� < ��−1 + �。

接下来�行，每行两个整数���� , ����� 0 ≤ � ≤ � − 1 ，保证����� ≤ ���� 。

输出格式 一行，一个整数，表示答案。注意答案可能为负数，你可能通过卖糖果赚钱。

样例输入 1 4 9 6 7 13 18 10 7 8 4 3 2 5 4 5 4

样例输出 1 105

样例输入输出 2 见下发文件。

共 10 组数据。

测试点 1,2 满足 1 ≤ � ≤ 100, � ≤ 100。

测试点 3,4 满足 1 ≤ � ≤ 100。

测试点 5,6 满足 1 ≤ � ≤ 103 , � ≤ 103 。

对于 100% 的数据，满足 1 ≤ � ≤ 2 × 105 , � ≤ 106 , 1 ≤ �� ≤ 109 , 0 ≤ ����� ≤ ���� ≤ 106 。