← 返回题目列表

Codeforces · 289/A

A. 企鹅波罗和片段

中文机器翻译题面 查看原题

小企鹅波罗喜欢整数段,即整数对 [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