天空可以看作是一个一维轴。月亮位于原点,坐标为$$$0$$$。
天空中漂浮着$$$n$$$ 云。每朵云都有相同的长度$$$l$$$。第 $$$i$$$ 最初覆盖 $$$(x_i, x_i + l)$$$ 的范围(排除端点)。最初,它以 $$$v_i$$$ 的速度移动,等于 $$$1$$$ 或 $$$-1$$$。
此外,最初没有一对云相交,即对于所有 $$$1 \leq i \lt j \leq n$$$、$$$\lvert x_i - x_j \rvert \geq l$$$。
风速为 $$$w$$$ 时,第 $$$i$$$ 云的速度变为 $$$v_i + w$$$。也就是说,它的坐标在每个单位时间内增加$$$v_i + w$$$。请注意,风可能很强,云可能会改变方向。
你要帮助 Mino 计算 $$$(i, j)$$$ ($$$i < j$$$) 对的数量,这样,在正确选择风速 $$$w$$$ 的绝对值不超过 $$$w_\mathrm{max}$$$ 的情况下(可能为负值和/或小数),第 $$$i$$$ 和第 $$$j$$$ 云都覆盖了未来同一时刻的月亮。这个 $$$w$$$ 在不同的配对中不需要相同。
输入
第一行包含三个空格分隔的整数 $$$n$$$、$$$l$$$ 和 $$$w_\mathrm{max}$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq l, w_\mathrm{max} \leq 10^8$$$) — 云的数量,每个云的长度分别为云量和最大风速。
以下 $$$n$$$ 行中的第 $$$i$$$ 包含两个空格分隔的整数 $$$x_i$$$ 和 $$$v_i$$$ ($$$-10^8 \leq x_i \leq 10^8$$$, $$$v_i \in \{-1, 1\}$$$) - 的初始位置和速度分别是第 $$$i$$$ 个云。
输入保证对于所有 $$$1 \leq i \lt j \leq n$$$,$$$\lvert x_i - x_j \rvert \geq l$$$。
输出
输出一个整数 - 无序云对的数量,这样在正确选择风速 $$$w$$$ 的情况下,每对云有可能在未来的同一时刻覆盖月球。
示例
输入 #1
5 1 2 -2 1 2 1 3 -1 5 -1 7 -1
输出 #1
4
输入 #2
4 10 1 -20 1 -10 -1 0 1 10 -1
输出 #2
1
注意
在第一个示例中,云的初始位置和速度如下所示。
这些对是:
- $$$(1, 3)$$$,在 $$$2.5$$$ 时刻覆盖月亮,$$$w = -0.4$$$;
- $$$(1, 4)$$$,在 $$$3.5$$$ 时刻覆盖月亮,$$$w = -0.6$$$;
- $$$(1, 5)$$$,在 $$$4.5$$$ 时刻覆盖月亮,$$$w = -0.7$$$;
- $$$(2, 5)$$$,在 $$$2.5$$$ 时刻覆盖月球,$$$w = -2$$$。
下面是 $$$2.5$$$ 时刻云的位置,$$$w = -0.4$$$。此时,$$$1$$$-st 和 $$$3$$$-rd 云都覆盖了月球。
在第二个示例中,唯一的一对是 $$$(1, 4)$$$,在 $$$15$$$ 时刻覆盖月球,$$$w = 0$$$。
请注意,上面给出的所有时间和风速只是无数选择中的示例。