题目描述

雪豹记不清自己做了多少题，只记得一开始做了多少题，后续在某一段时间做了多少。一天晚上他睡不着觉就开始数自己在 $n$ 天之内过了多少道ACM题，因为他想获得小红花。小红花是通过利用过题数去换来的，只要在任意两天（必须选两天）的过题数总和大于等于 $k$，就可以获得一个小红花，不能重复利用每天的过题数。但是雪豹笨啊，不知道自己能获得多少小红花。所以想问问你，雪豹最多能获得多少小红花。

输入格式

第一行为 $n,m,k$ ($n$ 为一共有多少天，$m$ 为一共有多少次插入，$k$ 为需要大于等于的过题数量）

接下来一行，给出 $n$ $(1 \leq n \leq 2 \times 10^5)$ 个整数，$a_i$ $(1 \leq a_i \leq 10^9)$ 表示为第 $i$ 天过的题数

接下来 $m$ 行，分别输入 $l,r,x$ 表示为在 $[l, r]$之内（包括 $l,r$ 这两天），每天的过题数量为 $x$

输出格式

输出一个整数，表示最多能获得的小红花的数量。

样例输入输出

5 2 4
1 3 2 4 1
1 3 1
4 5 1

2