题目描述

随着盛夏的到来，小 Rei 迎来了长达 $n$ 天的假期。为了充分利用这段时间，她计划每天骑共享单车出门，享受户外的清新空气。根据小 Rei 的计划，第 $i$ 天她将会骑行 $s_i$ 分钟，而每分钟的骑行费用为 $c$ 元。

为了节约开支，小 Rei 打算购买 APP 中提供的一些骑行卡。她了解到现在有 $m$ 种骑行卡可以购买，其中第 $i$ 种骑行卡的具体信息如下：

• 售价 $w_i$：每张卡的价格为 $w_i$ 元；
• 有效期 $d_i$：从购买当天算起，连续 $d_i$ 天内有效；
• 免费时间 $t_i$：在有效期内，每天的前 $t_i$ 分钟骑行是免费的。

小 Rei 可以多次购买任意一种骑行卡，并且可以在同一时间持有多张有效的骑行卡。如果某天有多张骑行卡同时有效，那么当天可以享受的免费骑行时间为这些卡中 $t_i$ 的最大值。超出免费时间的部分，仍然按照每分钟 $c$ 元计算。

小 Rei 希望在假期中尽可能减少骑行的总支出。请你帮助她计算出在假期中骑行的最小总支出是多少。

输入格式

从标准输入读入数据。

第一行包含三个整数 $n, m, c \; (1\le n\le 150, 1\le m, c\le 10^4)$，分别表示假期的天数，骑行卡的种类数以及每分钟的骑行费用。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 天骑行的分钟数 $s_i \; (1 \le s_i\le 150)$。

接下来的 $m$ 行，每行包含三个整数 $w_i, d_i, t_i \; (1\le w_i\le 10^9, 1\le d_i\le n, 1\le t_i\le 150)$，分别表示第 $i$ 种骑行卡的售价，有效期天数以及免费骑行时间。

输出格式

输出到标准输出。

输出一个整数，表示小 Rei 在假期中骑行的最小总支出。

样例

输入

5 2 2
30 40 50 20 10
10 3 20
15 2 30

输出

100

解释

小 Rei 的最优策略为：在第一天和第二天购买第二种骑行卡，在第三天购买第一种骑行卡。此时前三天的免费时间为 $30$ 分钟，后两天的免费时间为 $20$ 分钟，还需要在第二天额外支付 $10$ 分钟的骑行费用，在第三天额外支付 20 分钟的骑行费用。购买骑行卡共花费 $15+15+10=40$ 元，额外骑行费用为 $(10 + 20) \times 2 = 60$ 元，总支出为 $100$ 元。可以证明不存在总支出更少的方案，故输出 $100$。

样例

输入

8 4 1
5 10 9 3 9 8 3 1
11 4 5
12 7 4
10 2 9
5 3 4

输出

33