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% 的数据，�≤20，�≤20。

对于 50% 的数据（包括上部分的数据），�� 全部为 1。

对于 70% 的数据（包括上部分的数据），�≤100，�≤1000。

对于 100% 的数据，�≤1000，�≤10000，1≤��≤��≤�，其余数据均 ≤10000。

Source/Category

SubmitSubmit RecordStatisticsShowOff!