Polo the Penguin and Segments

题意翻译

- 给定 $n$ 个闭区间 $[l_i, r_i]$； - 每次操作你可以将任意一个区间 $[l, r]$ 扩展，即变为 $[l - 1, r]$ 或 $[l, r + 1]$； - 求使所有区间包含的整数数量之和被 $k$ 整除的最小操作次数。 Translated by [KHIN](/user/236807).

题目描述

Little penguin Polo adores integer segments, that is, pairs of integers $ [l; r] $ $ (l<=r) $ . He has a set that consists of $ n $ integer segments: $ [l_{1}; r_{1}],[l_{2}; r_{2}],...,[l_{n}; r_{n}] $ . We know that no two segments of this set intersect. In one move Polo can either widen any segment of the set 1 unit to the left or 1 unit to the right, that is transform $ [l; r] $ to either segment $ [l-1; r] $ , or to segment $ [l; r+1] $ . The value of a set of segments that consists of $ n $ segments $ [l_{1}; r_{1}],[l_{2}; r_{2}],...,[l_{n}; r_{n}] $ is the number of integers $ x $ , such that there is integer $ j $ , for which the following inequality holds, $ l_{j}<=x<=r_{j} $ . Find the minimum number of moves needed to make the value of the set of Polo's segments divisible by $ k $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1<=n,k<=10^{5} $ ). Each of the following $ n $ lines contain a segment as a pair of integers $ l_{i} $ and $ r_{i} $ ( $ -10^{5}<=l_{i}<=r_{i}<=10^{5} $ ), separated by a space. It is guaranteed that no two segments intersect. In other words, for any two integers $ i,j $ $ (1<=i&lt;j<=n) $ the following inequality holds, $ min(r_{i},r_{j})&lt;max(l_{i},l_{j}) $ .

输出格式

In a single line print a single integer — the answer to the problem.

输入输出样例

输入样例 #1

2 3
1 2
3 4

输出样例 #1

2

输入样例 #2

3 7
1 2
3 3
4 7

输出样例 #2

0