我们假定澄闪的技能是在一瞬间将全场清屏，技能的冷却时间是 秒。主播会选择一个时间开启技能，并且之后每当技能冷却时间结束后就会立即开启技能。具体地说，主播会选择一个非负整数时刻 ，而后在 这些时刻内分别在一瞬间消灭当前位于场上的所有敌方单位。
现在有 个敌方单位。第 个敌人会在 时刻进入场内并停留到 时刻（包含 时刻），如果在这期间没有消灭这个敌人，他将消耗我方基地 点生命值。
屏幕前的锐哥想知道，在主播无比聪明的前提下，我方最少会消耗多少点生命值。
第一行两个正整数 ，含义如上。
接下来 行，每行两个整数，其中的第 行三个整数表示 ，含义如上。
唯一一行一个整数，表示我方消耗的最少生命值。
4 5 1 3 2 4 4 4 1 6 2 12 15 10
2
选择 ，可以在 这些时刻消灭位于场上的所有敌人。只有第一个敌人无法被消灭，消耗 点生命值。
对于 的测试数据，。
对于 的测试数据，
