Bob 最近迷上了一款名为《王者荣耀》（Glory of Kings）的游戏。

他计划使用游戏币购买英雄皮肤。在第 $i$ 天，Bob 需要 $a_i$ 个游戏币来购买皮肤。获取游戏币有两种方式：

1. 每个游戏币可以直接以 $t$ 元的价格购买。
2. Bob 可以购买一张金币卡，在有效期内每天获得一些免费的临时游戏币。例如，在第 $i$ 天购买一张金币卡，该卡每天提供 $w$ 个免费临时游戏币，有效期为 $d$ 天，则 Bob 可以从第 $i$ 天到第 $i+d-1$ 天每天获得 $w$ 个临时游戏币。注意，临时游戏币意味着如果 Bob 在第 $x$ 天获得了临时游戏币，他只能在第 $x$ 天使用，这些临时游戏币会在第 $x+1$ 天过期。

《王者荣耀》中有 $n$ 种不同的金币卡。第 $i$ 种金币卡每天提供 $w_i$ 个免费临时游戏币，有效期为 $d_i$ 天，价格为 $c_i$ 元。

每种卡在任何一天都可以无限次购买。但是，任何新购买的金币卡都会覆盖之前购买的卡，即使之前的卡仍在有效期内。例如，如果 Bob 在第 $x$ 天开始时没有任何金币卡，他依次购买了金币卡 $i$ 和金币卡 $j$，那么他在第 $x$ 天将拥有 $w_i + w_j$ 个临时游戏币，但在第 $x$ 天结束时，他只会拥有金币卡 $j$（卡 $i$ 被卡 $j$ 覆盖）。

Bob 想知道，在采取最优策略的情况下，他为了实现计划最少需要支付多少钱。

输入格式

第一行包含三个整数 $m, n, t$ ($1 \le m \le 10^5, 1 \le n \le 400, 1 \le t \le 10^9$)，分别表示天数、金币卡种类数以及购买一个游戏币的价格。

接下来一行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$ ($0 \le a_i \le 5 \times 10^5$ 且 $\sum_{i=1}^m a_i \le 5 \times 10^5$)，表示 Bob 在 $m$ 天内每天需要的游戏币数量。

最后 $n$ 行描述 $n$ 种金币卡。第 $i$ 行包含三个整数 $c_i, w_i, d_i$ ($1 \le c_i, w_i, d_i \le 10^9$)，分别表示价格、每天提供的免费临时游戏币数量以及该种金币卡的有效期。

输出格式

输出一行一个整数，表示 Bob 采取最优策略所需支付的最小金额。

样例

样例输入 1

3 2 9
2 7 4
10 2 3
20 4 3

样例输出 1

39

样例输入 2

3 2 8
10 23 10
20 10 3
10 2 2

样例输出 2

58