Только что завершился Берляндский региональный отбор к ICPC. Было \(m\) участников, пронумерованных от \(1\) до \(m\), которые решали \(n\) задач, пронумерованных от \(1\) до \(n\).
Сейчас будет проходить разбор. Два автора задач готовы разобрать по \(k\) последовательных задач каждый. Авторы выбирают отрезки из \(k\) последовательных задач независимо друг от друга. Отрезки могут совпадать, пересекаться или не пересекаться вообще.
\(i\)-й участник хочет послушать разбор всех последовательных задач с \(l_i\) по \(r_i\). Каждый участник всегда выбирает слушать разбор только того автора, который расскажет большее количество интересных ему задач. Пусть это количество будет равно \(a_i\). Никто не может слушать разбор обоих авторов, даже если их отрезки не пересекаются.
Авторы задач хотят выбрать отрезки из \(k\) последовательных задач для себя так, чтобы сумма \(a_i\) по всем участникам была как можно больше.
Выходные данные
Выведите одно целое число — наибольшую возможную сумму \(a_i\) по всем участникам.
Примечание
В первом примере первый автор может рассказать разбор по задачам с \(1\) по \(3\), а второй — с \(6\) по \(8\). Тогда последовательность \(a_i\) будет \([3, 2, 3, 3, 3]\). Обратите внимание, что последний участник не может послушать обоих авторов, он выбирает только того, кто расскажет ему больше интересующих его задач.
Во втором примере первый может рассказать задачи с \(2\) по \(4\), а второй — с \(4\) по \(6\).
В третьем примере первый может рассказать задачи с \(1\) по \(1\), а второй — с \(2\) по \(2\). Или с \(4\) по \(4\) и с \(3\) по \(3\). Любая пара различных задач даст одинаковую сумму \(2\).
В четвертом примере первый может рассказать задачи с \(1\) по \(5\) и второй тоже с \(1\) по \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 5 3
1 3
2 4
6 9
6 9
1 8
|
14
|
|
2
|
10 3 3
2 4
4 6
3 5
|
8
|
|
3
|
4 4 1
3 3
1 1
2 2
4 4
|
2
|
|
4
|
5 4 5
1 2
2 3
3 4
4 5
|
8
|