BaoBao 开了一家商店，店里有 $n$ 件商品，编号为 $1, 2, \dots, n$。第 $i$ 件商品的价值为 $v_i$，价格为 $a_i$ 美元。JB 计划明天去 BaoBao 的商店。JB 总是以最优方式购买商品。假设 JB 有 $t$ 美元，他会购买一组商品，使得总价值最大化，且总价格不超过 $t$。

BaoBao 决定选择一对整数 $l$ 和 $r$（其中 $1 \le l \le r \le n$），并提高索引在 $[l, r]$ 范围内的所有商品的价格。当 JB 明天来时，对于 $l \le i \le r$ 的商品，他需要支付 $b_i$ 美元，而不是 $a_i$ 美元。

然而，BaoBao 不知道 JB 有多少钱，他只知道 $t$ 是在 $[1, k]$ 中均匀随机选择的一个整数。BaoBao 不希望 JB 买到太多好东西，他现在想知道，有多少对整数 $l$ 和 $r$ 可以满足：JB 购物清单的总价值的期望值 $\frac{f(1)+f(2)+\dots+f(k)}{k}$ 不超过 $E$，其中 $f(t)$ 表示当 JB 有 $t$ 美元时购物清单的总价值。请编写一个程序来帮助 BaoBao。

输入格式

输入仅包含一组数据。 第一行包含三个整数 $n, k$ 和 $E$（$1 \le n, k \le 200\,000$，$n \times k \le 10^7$，$1 \le E \le 10^9$）。 接下来的 $n$ 行，每行包含三个整数 $v_i, a_i$ 和 $b_i$（$1 \le v_i \le 10\,000$，$1 \le a_i < b_i \le k$），分别表示第 $i$ 件商品的价值、初始价格和提价后的价格。

输出格式

输出一行，包含一个整数，表示合法的整数对 $(l, r)$ 的数量。

样例

样例输入 1

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

样例输出 1

1

样例输入 2

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

样例输出 2

3