Вы играете в компьютерную игру, в которой есть \(n\) заданий, которые вам нужно выполнить. Однако \(j\)-е задание можно выполнить только в начале \(h_j\)-го часа игрового дня. Каждый игровой день длится ровно \(k\) часов. Часы каждого игрового дня пронумерованы числами \(0, 1, \ldots, k - 1\). После конца первого дня начинается следующий, и так далее.
Между заданиями есть зависимости: для некоторых пар \((a_i, b_i)\) задание с номером \(b_i\) может быть выполнено только после выполнения задания с номером \(a_i\). Гарантируется, что циклических зависимостей нет, поскольку иначе игру пройти было бы невозможно и никто не стал бы в неё играть.
Вы очень хорошо умеете играть в эту игру, поэтому вы можете выполнить любое число заданий за пренебрежимо малое время (т. е. вы можете выполнить любое число заданий в начале одного и того же часа, даже если между ними есть зависимости). Вам нужно выполнить все задания как можно быстрее. Вы можете выполнять их в любом доступном порядке. Время прохождения игры равно разнице между временем завершения последнего задания и временем завершения первого задания в этом порядке.
Найдите наименьшее время, за которое можно пройти игру.
Выходные данные
Для каждого набора входных данных выведите одно число — наименьшее время, необходимое для прохождения игры.
Примечание
В первом наборе входных данных задания \(1\) и \(4\) нужно выполнить в начале \(12\)-го часа дня, но они не могут быть выполнены в течение одного часа, поскольку между ними нужно выполнить задания \(2\) и \(3\). Однако всё это можно сделать за \(24\) часа. Для этого можно начать в \(12\) часов первого игрового дня, выполнив первое задание. В \(16\) часов можно выполнить задание \(2\). В \(18\) часов можно выполнить задание \(3\). Наконец, в \(12\) часов следующего дня можно выполнить задание \(4\). С момента выполнения первого задания до момента выполнения последнего прошло \(24\) часа.
В третьем наборе входных данных можно выполнить первое задание, а затем сразу же выполнить второе. Можно начать в \(5\) часов первого дня, выполнив первое задание. Сразу после этого становится доступным второе задание, его можно выполнять немедленно. Суммарное прошедшее время равно \(0\).
В четвёртом наборе входных данных можно начать с третьего задания. Можно начать в \(555\) часов первого дня и закончить в \(35\) часов второго дня. Суммарное прошедшее время равно \(1035-555=480\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4 4 24
12 16 18 12
1 2
1 3
2 4
3 4
4 3 10
2 6 5 9
1 4
2 4
3 4
2 1 10
5 5
1 2
5 0 1000
8 800 555 35 35
5 0 10
3 2 5 4 7
3 2 5
4 3 2
1 2
2 3
|
24
7
0
480
5
8
|