商店里有 件商品需要促销，每件商品的原价是 。现在有 种正在进行的促销，每种促销可以被表示为 ，，，表示当 商品被购买时，可以以价格 购买 商品，或当 商品被购买时，可以以价格 购买 商品。问购买所有促销商品需要花费最少的钱是多少。
第一行两个正整数 , ， 含义如题所述。
接下来一行 个正整数 ，表示商品的原价。
接下来 行，每行三个正整数 ， ，，表示促销关系。
一行一个正整数 ，表示最少花费。
5 3 2 4 3 5 6 1 2 2 1 3 1 1 4 7
16