D. Contact ATC

Codeforces

IDCF956D

Time1000ms

Memory256MB

Difficulty—

Arkady the air traffic controller is now working with _n_ planes in the air. All planes move along a straight coordinate axis with Arkady's station being at point 0 on it. The _i_\-th plane, small enough to be represented by a point, currently has a coordinate of _x__i_ and is moving with speed _v__i_. It's guaranteed that _x__i_·_v__i_ < 0, i.e., all planes are moving towards the station. Occasionally, the planes are affected by winds. With a wind of speed _v__wind_ (not necessarily positive or integral), the speed of the _i_\-th plane becomes _v__i_ + _v__wind_. According to weather report, the current wind has a steady speed falling inside the range \[ - _w_, _w_\] (inclusive), but the exact value cannot be measured accurately since this value is rather small — smaller than the absolute value of speed of any plane. Each plane should contact Arkady at the exact moment it passes above his station. And you are to help Arkady count the number of pairs of planes (_i_, _j_) (_i_ < _j_) there are such that there is a possible value of wind speed, under which planes _i_ and _j_ contact Arkady at the same moment. This value needn't be the same across different pairs. The wind speed is the same for all planes. You may assume that the wind has a steady speed and lasts arbitrarily long. ## Input The first line contains two integers _n_ and _w_ (1 ≤ _n_ ≤ 100 000, 0 ≤ _w_ < 105) — the number of planes and the maximum wind speed. The _i_\-th of the next _n_ lines contains two integers _x__i_ and _v__i_ (1 ≤ |_x__i_| ≤ 105, _w_ + 1 ≤ |_v__i_| ≤ 105, _x__i_·_v__i_ < 0) — the initial position and speed of the _i_\-th plane. Planes are pairwise distinct, that is, no pair of (_i_, _j_) (_i_ < _j_) exists such that both _x__i_ = _x__j_ and _v__i_ = _v__j_. ## Output Output a single integer — the number of unordered pairs of planes that can contact Arkady at the same moment. [samples] ## Note In the first example, the following 3 pairs of planes satisfy the requirements: * **(2, 5)** passes the station at time 3 / 4 with _v__wind_ = 1; * **(3, 4)** passes the station at time 2 / 5 with _v__wind_ = 1 / 2; * **(3, 5)** passes the station at time 4 / 7 with _v__wind_ = - 1 / 4. In the second example, each of the 3 planes with negative coordinates can form a valid pair with each of the other 3, totaling 9 pairs.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Contact ATC",
    "description": {
      "content": "Arkady the air traffic controller is now working with _n_ planes in the air. All planes move along a straight coordinate axis with Arkady's station being at point 0 on it. The _i_\\-th plane, small eno",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF956D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Arkady the air traffic controller is now working with _n_ planes in the air. All planes move along a straight coordinate axis with Arkady's station being at point 0 on it. The _i_\\-th plane, small eno...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments