4857: [ZJOI2013] 防守战线

Memory Limit:512 MB Time Limit:3.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

战线可以看作一个长度为  的序列,现在需要在这个序列上建塔来防守敌兵,在序列第  号位置上建一座塔有  的花费,且一个位置可以建任意多的塔,费用累加计算。有  个区间 [1,1],[2,2],,[,],在第  个区间的范围内要建至少  座塔。求最少花费。

Input

第一行为两个数 ,

接下来一行,有  个数,描述  数组。

接下来  行,每行三个数 ,,,描述一个区间。

Output

仅包含一行,一个数,为最少花费。

Sample Input Copy

5 3
1 5 6 3 4
2 3 1
1 5 4
3 5 2

Sample Output Copy

11

HINT

【样例说明】

位置 1 建 2 个塔,位置 3 建一个塔,位置 4 建一个塔。花费 1×2+6+3=11

【数据规模】

对于 20% 的数据,2020

对于 50% 的数据(包括上部分的数据), 全部为 1

对于 70% 的数据(包括上部分的数据),1001000

对于 100% 的数据,1000100001,其余数据均 10000