Поликарп играет в компьютерную игру, в которой он управляет группой выживших в постапокалиптическом мире. Мир захвачен ордами зомби, которые рвутся на базу выживших. Зомби будут пытаться пробраться на базу выживших в течение $$$x$$$ минут, начиная с минуты $$$0$$$. Всего на базу есть $$$n$$$ входов, каждую минуту через каждый вход пытается пробраться один зомби.

Чтобы ограничить вторжение зомби, выжившие могут охранять входы на базу. Есть два варианта:

• вручную — отстреливать зомби на определенном входе;
• автоматически — установить электрическую сетку на определенном входе, чтобы поджаривать зомби.

Если в течение какой-то минуты вход охраняется любым или обоими способами, в эту минуту зомби не пробираются на базу через этот вход.

Каждый вход охраняется одним из выживших. $$$i$$$-й вход охраняется с минуты $$$l_i$$$ по минуту $$$r_i$$$ не включительно — $$$[l_i, r_i)$$$.

В распоряжении выживших есть $$$k$$$ генераторов, при помощи которых можно охранять входы автоматически. Каждый вход должен быть подключён ровно к одному генератору, но при этом каждый генератор может запитать любое количество входов. Каждый генератор будет работать ровно $$$m$$$ минут подряд. Поликарп выбирает время запуска каждого генератора независимо друг от друга, этот интервал длиной $$$m$$$ минут должен вкладываться в интервал $$$[0, x)$$$.

Поликарп — не совсем нормальный игрок. Он хочет, чтобы игра была для него как можно сложнее. Поэтому он подключит каждый вход к генератору и настроит время работы генераторов так, чтобы как можно больше зомби пробралось на базу. Помогите ему это сделать!