8. Ostrovný maják

Neďaleko kalifornského pobrežia je ostrov. Má svoje meno, ale miestni mu hovoria Ostrov. Na ostrove je maják. V majáku žije jeho správca. Má svoje meno, ale miestni mu hovoria Maják.

Maják z majáku dovidí ľubovoľným smerom do tej istej vzdialenosti. Môže teda pozorovať, čo sa deje vo vnútri konkrétneho kruhu, ktorého stredom je samotný maják. Všade v tomto kruhu okrem samotného majáku je voda.

Kruhom sa raz za čas preplaví nejaká loď. Všetky lode sa plavia po priamke (z ktorej Maják vidí len úsečku). Maják si do databázy poctivo zapisoval, kedy, odkiaľ a kam sa ktorá loď plavila.

Občas sa stane, že sa okolo majáku plavia dve lode naraz. A v tých najvzrušujúcejších chvíľach to dokonca chvíľu vyzerá na kolíziu. Vtedy jedna z lodí musí spomaliť alebo zrýchliť. A Maják je celý preč od radosti, že sa konečne niečo zaujímavé deje.

Po poslednej oslave Majákovych narodenín však s kamarátmi blbli, menili heslá a z databázy zmazali stĺpec s časmi. Na nové heslá si ešte Maják ráno horko-ťažko spomenul, časy do databázy mu už ale nik nevráti.

Úloha

Na obvode kruhu, ktorý vidí Maják z majáku, rovnomerne rozmiestnime \(r\) bodov (kde \(r\) je nepárne). Idúc po obvode kruhu body očíslujeme od 0 po \(r-1\). Lodí sa doteraz okolo plavilo \(n\), tie očíslujeme od 0 po \(n-1\). O poradí lodí nič nevieme – napr. loď 3 mohla prejsť okolo skôr ako loď 47, neskôr ako loď 47, alebo zhruba v tom istom čase. Pre každé \(i\) platí, že loď \(i\) Maják prvýkrát uvidel v bode \(z_i\) a naposledy v bode \(k_i\).

Váš program dostane na vstupe vyššie popísané údaje. Z nich by mal vypočítať počet dvojíc lodí \(i<j\) takých, že je možné, že sa lode \(i\) a \(j\) museli jedna druhej prispôsobiť aby zabránili kolízii.¹ Pochopiteľne, lode považujte pri riešení úlohy za body.

Formát vstupu

V prvom riadku je číslo \(n\) udávajúce počet lodí. V druhom riadku je číslo \(r\) udávajúce počet bodov na obvode kruhu (pričom \(r\) je nepárne číslo² väčšie ako \(2n\)).

Nasleduje \(n\) riadkov, každý z nich popisuje jednu loď: obsahuje jej čísla \(z_i\) a \(k_i\). Platí \(0\leq z_i<r\) a \(0\leq k_i<r\). Navyše platí, že všetky hodnoty \(z_i\) a \(k_i\) sú navzájom rôzne. (Vstup teda obsahuje \(2n\) rôznych súradníc.)

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo: počet dvojíc lodí, ktoré sa mohli vo vnútri kruhu stretnúť.

Hodnotenie

Je päť sád vstupov.

Maximálne počty lodí v týchto sadách sú 20, \(75\,000\), \(200\,000\), \(75\,000\) a \(200\,000\).

Maximálne hodnoty \(r\) v týchto sadách sú 1000, \(10^6\), \(10^{18}\), \(10^{18}\) a \(10^{18}\).

Navyše v tretej sade platí, že všetky vstupy sú generované rovnomerne náhodne (každé z čísel \(z_i\) a \(k_i\) je zvolené náhodne spomedzi všetkých ešte nepoužitých).

Príklady

Input:

3
101
10 20
15 25
70 60

Output:

1

Lode 0 a 1 sa mohli stretnúť, ak sa plavili okolo majáku s Majákom zhruba v tom istom čase.

Input:

3
101
97 3
6 94
91 10

Output:

0

Input:

4
101
0 50
25 75
20 80
82 22

Output:

4