Cerința

Dându-se n fracții ireducitibile sortate crescător și un număr k să se determine numărul de subșiruri de exact k elemente în care diferența dintre două fracții consecutive este egală cu 1. De asemenea, prima fracție din subșir trebuie să nu fie supraunitara.

Date de intrare

Fișierul de intrare fractii3.in conține pe prima linie numerele n și k, iar pe următoarele n linii câte două numere a și b, reprezentând numărătorul și numitorul unei fracții.

Date de ieșire

Fișierul de ieșire fractii3.out va conține pe prima linie numărul S, reprezentând numărul de subșiruri.

Restricții și precizări

• 1 ≤ k ≤ n ≤ 1.000.000
• 1 ≤ a, b ≤ 10.000
• 0 < \({a \over b}\) ≤ k
• Fracțiile sunt sortate și nu vor exista două fracții consecutive cu aceeași valoare.
• Pentru 20% din punctaj, n ≤ 10

Exemplu:

fractii3.in

6 3
1 3
1 2
7 8
4 3
3 2
5 2

fractii3.out

1

Explicație

Doar subșirul format din fracțiile \({1 \over 2}, {3 \over 2}, {5 \over 2}\) este valid.