题目描述
小明喜欢边玩手机边走回家，我们设小明手机的电池容量为 T。在小明回家的路上有 n+1 家奶茶店，每家都有充电宝， 0是起点 N是终点，小明每走一个单位距离消耗1 个单位的电量。给出每个奶茶店到下一家奶茶店的距离D ，以及充单位电量的花费P ，求一次回家的最少花费。如果小明不能全程玩手机回家，那么你就要帮他戒网瘾，输出 -1。
一开始小明的手机的电量为0 。
输入格式
第一行两个数整数 N,T 中间用空格分隔，N+1 为奶茶店的数量， T为手机电池容量。
第二至N+1 行：每行 2 个数Di，Pi ，中间用空格分隔，分别表示到下一家奶茶店的距离和充电的单价。
输出格式
输出回家的最小费用，如果不能全程玩手机回家，输出 -1。
样例
样例输入
3 15
10 2
9 1
8 3
样例输出
41
数据范围与提示
对于30%的数据，N<=50
对于100%的数据，N<=5*10^5,1<=Di,Pi<=10^6
【参考程序】
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 501005
#define ll long long
int n, m, i, r, now, d[N], p[N], q[N], nxt[N];
ll dis, ans, sum[N];
int main() {freopen("wayhome.in", "r", stdin);freopen("wayhome.out", "w", stdout);scanf("%d%d", &n, &m);for (i = 1; i <= n; i++)scanf("%d%d", &d[i], &p[i]), sum[i] = sum[i - 1] + 1ll * d[i];for (i = n; i; i--) {while (r && p[q[r]] > p[i]) r--;nxt[i] = q[r];q[++r] = i;if (!nxt[i])nxt[i] = n + 1;}ans = 0;now = 0;for (i = 1; i <= n; i++) {now -= d[i - 1];if (now < 0) {puts("-1");return 0;}dis = min(sum[nxt[i] - 1] - sum[i - 1], 1ll * m);if (dis > now)ans += 1ll * (dis - now) * p[i], now = dis;}printf("%lld\n", ans);return 0;
}