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: [l1; r1], [l2; r2], ..., [ln; rn]. 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 [l1; r1], [l2; r2], ..., [ln; rn] is the number of integers x, such that there is integer j, for which the following inequality holds, lj ≤ x ≤ rj.

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 ≤ 105). Each of the following n lines contain a segment as a pair of integers li and ri ( - 105 ≤ li ≤ ri ≤ 105), 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(ri, rj) < max(li, lj).

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
from __future__ import division;
from bisect import *;
from fractions import Fraction;
import sys;
import math;
import io;

INF = 987654321987654321987654321;

def readint(delimiter=' ') :
	return map(int, raw_input().split(delimiter));

def readstr() :
	return raw_input().split();

def readfloat() :
	return map(float, raw_input().split());

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

'''
Create multidimentional list easily

How to Use :
arr = dlist([1st dimension, 2nd, ... ], 0 as base);
'''
def dlist(args, base=0) :
    arr_args = args;
    
    def rec(arr) :      
        if len(arr) == 1 :
            return [base for _ in xrange(arr[0])];
        else :
            temp_arr = rec(arr[1:]);
            print arr[0], temp_arr;
            return [temp_arr for _ in xrange(arr[0])];
    return rec(arr_args);

def bin_search(a, x, left, right) :

    while left<=right :
        mid = (left + right)//2;
        
        if a[mid] == x :
            return mid;
        elif a[mid] < x :
            left = mid + 1; 
        elif a[mid] > x :
            right = mid - 1;
                       
        pass
    
    return -1;
    pass

if __name__ == '__main__':
	
    n, k = readint();
    total = 0;
    for ii in xrange(n) :
        a, b = readint();
        total += (b-a+1);

    print int(k*math.ceil(total/k))-(total);

    pass