战线可以看作一个长度为 的序列，现在需要在这个序列上建塔来防守敌兵，在序列第 号位置上建一座塔有 的花费，且一个位置可以建任意多的塔，费用累加计算。有 个区间 ，在第 i 个区间的范围内要建至少 座塔。求最少花费。
第一行为两个数 。接下来一行，有 个数，描述 数组。接下来 行，每行三个数 ，描述一个区间。
仅包含一行，一个数，为最少花费。
5 3 1 5 6 3 4 2 3 1 1 5 4 3 5 2
11
位置 建 个塔，位置 建一个塔，位置 建一个塔。花费 。
对于 的数据，，。
对于 的数据（包括上部分的数据）， 全部为 。
对于 的数据（包括上部分的数据），，。
对于 的数据，，，，其余数据均。
