← 返回题目列表

Codeforces · 76/F

F. 旅游

中文机器翻译题面 查看原题

游客沿着 X 轴行走。他可以选择两个方向和不超过V的任何速度。他也可以站立不动。他从报纸上知道,在时间 t1 时,坐标 x1 的点将发生一个有趣的事件,在时间 t2 时,坐标 x2 的点将发生另一个事件,依此类推,直到 (xn, tn)。有趣的事件很短,所以我们可以假设它们是立即发生的。如果游客在时间 ti 位于坐标 xi 的点,则事件 i 被计数。

编写旅游程序,在以下情况下找到最大数量的旅游事件:

- 开始时(当时间等于0时)游客出现在点0,
- 游客可以自己选择起始点。

是的,您应该回答两个相似但不同的问题。

输入

输入的第一行包含单个整数 N (1 ≤ N ≤ 100000) — 有趣事件的数量。接下来的 N 行包含两个整数 xi 和 ti — 第 i 个事件的坐标和时间。输入的最后一行包含整数 V — 游客的最大速度。所有 xi 将在 - 2·108 ≤ xi ≤ 2·108 范围内,所有 ti 将在 1 和 2·106 之间(包括 1 和 2·106)。 V 将为正数,并且不会超过 1000。输入可能包含同时发生或在同一地点但不同时在同一地点发生的事件。

输出

输出的唯一一行应包含两个空格分隔的整数 - 游客在时间 0 从点 0 开始移动时可以访问的最大事件数,以及如果他自己选择初始点,游客可以访问的最大事件数。

示例

输入 #1

3
-1 1
42 7
40 8
2

输出 #1

1 2