No tag edit access

A. Polo the Penguin and Segments

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLittle 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*.

Input

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* < *j* ≤ *n*) the following inequality holds, *min*(*r*_{i}, *r*_{j}) < *max*(*l*_{i}, *l*_{j}).

Output

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

Examples

Input

2 3

1 2

3 4

Output

2

Input

3 7

1 2

3 3

4 7

Output

0

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/19/2020 09:03:00 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|