Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

E. Два разбора
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Только что завершился Берляндский региональный отбор к ICPC. Было $$$m$$$ участников, пронумерованных от $$$1$$$ до $$$m$$$, которые решали $$$n$$$ задач, пронумерованных от $$$1$$$ до $$$n$$$.

Сейчас будет проходить разбор. Два автора задач готовы разобрать по $$$k$$$ последовательных задач каждый. Авторы выбирают отрезки из $$$k$$$ последовательных задач независимо друг от друга. Отрезки могут совпадать, пересекаться или не пересекаться вообще.

$$$i$$$-й участник хочет послушать разбор всех последовательных задач с $$$l_i$$$ по $$$r_i$$$. Каждый участник всегда выбирает слушать разбор только того автора, который расскажет большее количество интересных ему задач. Пусть это количество будет равно $$$a_i$$$. Никто не может слушать разбор обоих авторов, даже если их отрезки не пересекаются.

Авторы задач хотят выбрать отрезки из $$$k$$$ последовательных задач для себя так, чтобы сумма $$$a_i$$$ по всем участникам была как можно больше.

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

В первой строке записаны три целых числа $$$n, m$$$ и $$$k$$$ ($$$1 \le n, m \le 2000$$$, $$$1 \le k \le n$$$) — количество задач, количество участников и длина отрезка задач, разбор на которые планирует рассказать каждый из авторов.

В $$$i$$$-й из следующих $$$m$$$ строк записаны по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — отрезок задач, разбор на которые хочет послушать $$$i$$$-й участник.

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

Выведите одно целое число — наибольшую возможную сумму $$$a_i$$$ по всем участникам.

Примеры
Входные данные
10 5 3
1 3
2 4
6 9
6 9
1 8
Выходные данные
14
Входные данные
10 3 3
2 4
4 6
3 5
Выходные данные
8
Входные данные
4 4 1
3 3
1 1
2 2
4 4
Выходные данные
2
Входные данные
5 4 5
1 2
2 3
3 4
4 5
Выходные данные
8
Примечание

В первом примере первый автор может рассказать разбор по задачам с $$$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$$$.