小企鹅波罗喜欢整数段,即整数对 [l; r] (l≤r)。
他有一个由n个整数段组成的集合:[l1; r1],[l2; r2],...,[ln; rn]。我们知道这个集合中没有任何两个线段相交。在一次移动中,Polo 可以将集合中的任何一段向左加宽 1 个单位或向右加宽 1 个单位,即变换 [l; r] 到任一段 [l - 1; r],或分段 [l; r + 1]。
由 n 个段组成的一组段的值 [l1; r1],[l2; r2],...,[ln; rn] 是整数 x 的数量,使得存在整数 j,其中以下不等式成立,lj ≤ x ≤ rj。
求使 Polo 线段集合的值能被 k 整除所需的最小移动次数。
输入
第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 105)。以下 n 行中的每一行都包含一个段,作为一对整数 li 和 ri (- 105 ≤ li ≤ ri ≤ 105),用空格分隔。
保证没有两个线段相交。换句话说,对于任意两个整数 i, j (1 ≤ i < j ≤ n),以下不等式成立,min(ri, rj) < max(li, lj)。
输出
在一行中打印一个整数——问题的答案。
示例
输入 #1
2 3 1 2 3 4
输出 #1
2
输入 #2
3 7 1 2 3 3 4 7
输出 #2
0