H. 促销活动

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

商店里有 件商品需要促销,每件商品的原价是 。现在有 种正在进行的促销,每种促销可以被表示为 ,表示当 商品被购买时,可以以价格 购买 商品,或当 商品被购买时,可以以价格 购买 商品。问购买所有促销商品需要花费最少的钱是多少。

输入格式

第一行两个正整数 , , 含义如题所述。

接下来一行 个正整数 ,表示商品的原价。

接下来 行,每行三个正整数 ,表示促销关系。

输出格式

一行一个正整数 ,表示最少花费。

样例

样例输入

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

样例输出

16

数据范围与提示