该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

程老师的花房里有一排花坛，从左到右编号 $1$ 到 $n$，每个花坛里都插着一根水位标尺。这一排花坛刚刚整备过，所有花坛的初始水量都是 $0$ 升。

这一周的浇水由值日生负责，每浇一次就在本子上记一行：从第 $l_i$ 个花坛到第 $r_i$ 个花坛，每个花坛各浇 $v_i$ 升（是每个花坛都浇这么多，不是这一段总共这么多）。水浇下去就渗进土里，不会被分走，也不会蒸发，所以每个花坛的水量只会增加、不会减少。本子上一共记了 $q$ 行。

周末程老师要检查这批花的生长情况，他想知道：第几次浇水之后，首次出现水量达到 $H$ 升的花坛。这里"第几次"指的是浇水记录里的序号，首次出现指的是这个序号尽可能小。如果 $q$ 次浇水全部结束都没有任何一个花坛的水量达到 $H$ 升，就说明这批花还得再等等，请输出 -1。

输入格式

从文件 water.in 中读入数据。

第一行三个整数 $n, q, H$。

接下来 $q$ 行，每行三个整数 $l_i, r_i, v_i$，表示第 $i$ 次浇水的范围和每坛水量。

输出格式

输出到文件 water.out 中。

一行一个整数，表示首次出现水量达到 $H$ 升的花坛是在第几次浇水之后；若始终没有出现，输出 -1。

数据范围

特殊性质 A：每次浇水都有 $l_i = 1$ 且 $r_i = n$。

特殊性质 B：每次浇水都有 $v_i = 1$。

对于所有测试点：$1 \le n, q \le 10^5$，$1 \le l_i \le r_i \le n$，$1 \le v_i \le 10^4$，$1 \le H \le 10^{14}$。

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

4

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

-1

样例解释

样例 1 与 样例 2 的浇水记录完全相同，只差 $H$ 的取值。逐个花坛记录每次浇水后的水量：

• 第 $1$ 次（给 $1$ 到 $3$ 号各浇 $4$ 升）后：$[4, 4, 4, 0, 0]$，最大 $4$ 升；
• 第 $2$ 次（给 $2$ 到 $4$ 号各浇 $3$ 升）后：$[4, 7, 7, 3, 0]$，最大 $7$ 升；
• 第 $3$ 次（给 $3$ 到 $5$ 号各浇 $2$ 升）后：$[4, 7, 9, 5, 2]$，最大 $9$ 升；
• 第 $4$ 次（给 $1$ 到 $2$ 号各浇 $3$ 升）后：$[7, 10, 9, 5, 2]$，最大 $10$ 升。

样例 1 中 $H = 10$，前三次最多 $9$ 升还没到，第 $4$ 次之后 $2$ 号花坛到了 $10$ 升，所以答案是 $4$。样例 2 中 $H = 100$，四次浇完最多也只有 $10$ 升，所以输出 -1。