题目描述

最进，政府部门想要促进乡村现代化建设，大兴土木，又是修路，又是安装路灯等等，目前经费有点紧张，想要尽可能的节省经费做到最好的效果。

刚好有个安装路灯问题需要解决：

假设乡村每家每户都是以一条直线排列，而且每家有一个范围 [L, R] ,表示这家所占位置是在这条路的 L 到 R ，同时根据每家为政府部门的贡献不一，安装的路灯数目也不同（政府部门根据贡献并加以补偿作为此家安装路灯的经费）， 假设路是一条坐标轴，路灯只能安装到整数下标上，每家安装路灯等总数必定小于等于 R - L + 1 ，即使贡献超过安装路灯总价值。

要求在有限的贡献内最小安装路灯的数量，达到每家每户的贡献要求。

输入格式

输入包含多行，第一行包含 3 个整数 N ， P ， Q ，分别表示这条路上居户的户数，政府部门补偿金额和安装一台路灯需要的金额数目。

接下来的 N 行每行输入 3 个整数 L ， R， W ，表示这家居户所在位置和它的贡献（每家的 L R 可能存在交叉， 即 [2, 5] 和 [3, 6]）。

输出格式

输出一行答案表示最少需要安装多少台路灯， 并换行输出政府收益（可能为正或负）。

数据范围

1 ≤ N, Q ≤ 10^5

0 ≤ P ≤ 10^9

1 ≤ L ≤ R ≤ 10^9

Q ≤ W ≤ 10^9

样例

样例输入

3 0 1
2 3 1
5 5 1
5 6 2

样例输出

3
1

解释

第一家居户：选择在 2 或 3 位置上安装路灯（总贡献 = 政府补贴 + 自己贡献 = 0 + 1 = 1， 可安装 ⌈总贡献 / Q⌉ = ⌈1 / 1⌉ = 1 台路灯 ）

第二家居户：选择在 5 位置上安装路灯（ ⌈(1 + 0) / 1⌉ = 1台 ）

第三家居户：选择在 5、6 位置上安装路灯（ ⌈(2 + 0) / 1⌉ = 2台 ）

因此政府仅需在 2、5、6 或 3、5、6 三个位置安装路灯即可，保证安装数量最少

政府收益为：（1 + 1 + 2）- （3 * 1） = 1

样例输入

3 1 1
1 3 1
2 5 2
5 6 1

样例输出

4
0

解释

第一家居户：选择在 2、3 位置上安装路灯（ ⌈(1 + 1) / 1⌉ = 2台 ）

第二家居户：选择在 2、3、5 位置上安装路灯（ ⌈(1 + 2) / 1⌉ = 3台 ）

第三家居户：选择在 5、6 位置上安装路灯（ ⌈(1 + 1) / 1⌉ = 2台 ）

因此政府仅需在 2、3、5、6 四个位置安装路灯即可，保证安装数量最少

政府收益为：（1 + 2 + 1）- （4 * 1） = 0

温馨提示： 如果一家居户位于 [3, 5] ，此范围内最多安装 5 - 3 + 1 = 3 台路灯， 即使贡献超过三台路灯的价值；数据范围过大，请采用 long long。

时限： 300ms
出题人： dreamy-xay