eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Русское лото

Русское лото

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

Для игры в "русское лото" используются карточки,удовлетворяющие условиям:

  • карточка состоит из 3-х строк и N столбиков;

  • K клеток в каждой строке заняты целыми числами (остальные свободны);

  • в i-м столбце могут находится только числа из диапазона a_i...b_i;

  • одно и то же число не может повторятся на одной и той же карточке.

Пример карточки:

Найти количество различных карточек.

Входные данные

Впервой строке записано два числа - N и K (3K9, 1 < K < N). В каждой их следующих N строк записано два неотрицательных числа a_i и b_i, непревышающие 1000. Гарантировано, что a_i < b_i, b_i < a_{i+1} и b_i-a_i < 20.

Выходные данные

Программа должна вывести одно число - искомое количество карточек.

Пример

Входные данные #1
9 5
1 9
10 19
20 29
30 39
40 49
50 59
60 69
70 79
80 90
Выходные данные #1
817687046204481600000