Турист путешествует пешком вдоль координатной оси Ox. Идти можно в любом из двух возможных направлений и с любой скоростью, не превышающей V, в том числе находиться на месте. Из газетных анонсов он знает, что в момент t1 в точке с координатой x1 состоится одно интересное событие, в момент t2 в точке с координатой x2 — еще одно, и т. д., до (xN, tN). Интересные события достаточно кратковременны, их можно считать мгновенными. Считается, что турист посетил событие i, если в момент ti он находился в точке с координатой xi.
Напишите программу, которая найдет максимальное количество событий, которые сможет посетить турист, для таких двух предположений: А) сначала движения (в момент времени 0) турист находится в точке 0; Б) турист может выбрать начальную точку, из которой он стартует.
Первая строка входного файла содержит единственное натуральное число N (1 ≤ N ≤ 100 000) — количество интересных событий. Последующие N строк содержат по два целых числа xi и ti — координату и момент времени события с номером i. Последняя (N + 2)-ая строка файла содержит единственное целое число V — значение максимальной скорости движения туриста. Все значения xi принадлежат диапазону - 2·108 ≤ xi ≤ 2·108, все значения ti принадлежат диапазану 1 ≤ ti ≤ 2·106, значение V принадлежит диапазону 1 ≤ V ≤ 1000. Во входных данных возможны различные события, имеющие одинаковую координату x или одинаковое время t, но невозможны различные события, имеющие одинаковые x и t одновременно.
Единственная строка выходного файла должна содержать два целых числа — максимально возможное количество событий, которые турист может посетить, если он начнет движение в момент 0 из точки 0, затем максимально возможное количество событий, которые турист может посетить, самостоятельно выбрав точку старта.
3
-1 1
42 7
40 8
2
1 2
Название |
---|