题目描述

小企鹅 Polo 非常喜欢整数区间，即形如 $[l; r]$ 的整数对（$l \leq r$）。

他有一个由 $n$ 个整数区间组成的集合：$[l_{1}; r_{1}], [l_{2}; r_{2}], \ldots, [l_{n}; r_{n}]$。已知集合中的任意两个区间都不相交。在一次操作中，Polo 可以将集合内的任意一个区间向左扩展 $1$ 个单位，或者向右扩展 $1$ 个单位，也就是将 $[l; r]$ 变为 $[l-1; r]$ 或者 $[l; r+1]$。

一组包含 $n$ 个区间 $[l_{1}; r_{1}], [l_{2}; r_{2}], \ldots, [l_{n}; r_{n}]$ 的集合的值，定义为有多少个整数 $x$，存在某个整数 $j$ 使得 $l_{j} \leq x \leq r_{j}$。

请你计算，为了使 Polo 的区间集合的值可以被 $k$ 整除，最少需要多少次操作。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 10^5$）。接下来 $n$ 行，每行包含一对整数 $l_{i}$ 和 $r_{i}$（$-10^5 \leq l_{i} \leq r_{i} \leq 10^5$），表示一个区间，两个整数用空格隔开。

保证任意两个区间都不相交。也就是说，对于任意的 $i,j$（$1 \leq i < j \leq n$），都有 $\min(r_{i}, r_{j}) < \max(l_{i}, l_{j})$。

输出格式

输出一个整数，表示答案。

说明/提示

由 ChatGPT 5 翻译

样例

2 3
1 2
3 4

2

3 7
1 2
3 3
4 7

0