#383. D - 消灭怪物
D - 消灭怪物
D - 消灭怪物
题目描述
有 只怪物排成一排,按从左到右的顺序编号为 到 。怪物 的初始生命值为 。
高桥拥有 张卷轴,编号为 到 。
使用第 张卷轴需要消耗 点魔力,并对编号在闭区间 内的每只怪物造成 点伤害。
高桥可以选择其中若干张卷轴,每张卷轴最多使用一次,目标是消灭所有怪物。当一只怪物受到的累计伤害大于或等于其初始生命值时,它就被消灭。
求消灭全部怪物所需的最小总魔力消耗;如果无论怎样选择卷轴都做不到,输出 -1。
输入格式
第一行输入两个整数 。
第二行输入 个整数 。
接下来 行,每行输入四个整数 。
输出格式
输出最小魔力消耗。如果无法消灭全部怪物,输出 -1。
数据范围
- 所有输入均为整数。
样例输入 1
3 3
5 10 5
1 3 5 10
2 2 5 3
1 3 10 15
样例输出 1
13
样例输入 2
4 3
10 10 10 20
1 2 10 5
2 3 10 5
3 4 10 5
样例输出 2
-1
样例输入 3
6 6
12 15 8 20 10 14
1 3 10 7
2 5 8 9
4 6 12 11
1 6 6 15
3 4 10 6
5 6 10 8
样例输出 3
39
样例输入 4
8 9
500000000 800000000 600000000 1000000000 700000000 900000000 400000000 300000000
1 4 400000000 100000000
3 8 500000000 200000000
1 8 300000000 250000000
5 7 400000000 80000000
2 5 300000000 90000000
1 2 500000000 120000000
7 8 200000000 50000000
4 6 400000000 110000000
1 8 600000000 400000000
样例输出 4
520000000
样例输入 5
1 1
1000000000
1 1 1000000000 1000000000
样例输出 5
1000000000