Поликарп играет в компьютерную игру, в которой он управляет группой выживших в постапокалиптическом мире. Мир захвачен ордами зомби, которые рвутся на базу выживших. Зомби будут пытаться пробраться на базу выживших в течение \(x\) минут, начиная с минуты \(0\). Всего на базу есть \(n\) входов, каждую минуту через каждый вход пытается пробраться один зомби.
Чтобы ограничить вторжение зомби, выжившие могут охранять входы на базу. Есть два варианта:
- вручную — отстреливать зомби на определенном входе;
- автоматически — установить электрическую сетку на определенном входе, чтобы поджаривать зомби.
Если в течение какой-то минуты вход охраняется любым или обоими способами, в эту минуту зомби не пробираются на базу через этот вход.
Каждый вход охраняется одним из выживших. \(i\)-й вход охраняется с минуты \(l_i\) по минуту \(r_i\) не включительно — \([l_i, r_i)\).
В распоряжении выживших есть \(k\) генераторов, при помощи которых можно охранять входы автоматически. Каждый вход должен быть подключён ровно к одному генератору, но при этом каждый генератор может запитать любое количество входов. Каждый генератор будет работать ровно \(m\) минут подряд. Поликарп выбирает время запуска каждого генератора независимо друг от друга, этот интервал длиной \(m\) минут должен вкладываться в интервал \([0, x)\).
Поликарп — не совсем нормальный игрок. Он хочет, чтобы игра была для него как можно сложнее. Поэтому он подключит каждый вход к генератору и настроит время работы генераторов так, чтобы как можно больше зомби пробралось на базу. Помогите ему это сделать!
Выходные данные
Выведите одно целое число — наибольшее количество зомби, которые могут пробраться на базу после того как Поликарп подсоединит каждый вход к некоторому генератору и выберет время для каждого генератора.