Маленький пингвин Поло очень любит целочисленные отрезки, то есть пары целых чисел [l; r] (l ≤ r).
У него есть множество, состоящее из n целочисленных отрезков: [l1; r1], [l2; r2], ..., [ln; rn]. Известно, что никакие два отрезка этого множества не пересекаются. За один шаг Поло может расширить любой отрезок множества на 1 влево или на 1 вправо, то есть из отрезка [l; r] получить либо отрезок [l - 1; r], либо — [l; r + 1].
Величиной множества отрезков, состоящего из n отрезков [l1; r1], [l2; r2], ..., [ln; rn], назовем количество целых чисел x таких, что существует целое число j, для которого выполняется неравенство, lj ≤ x ≤ rj.
Найдите минимальное количество шагов, которое требуется, чтобы величина множества отрезков Поло делилась на k.