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
//Date: Oct 8, 2013 
//Time: 8:58:07 PM

import java.util.*;
import java.io.*;

public class A289 implements Runnable {
	class Seg implements Comparable<Seg>{
		int l;
		int r;
		public Seg(int ll, int rr){
			l = ll;
			r = rr;
		}
		public int compareTo(Seg o){
			return l - o.l;
		}
	}
	public void solve() throws IOException {
		int N = nextInt();
		int K = nextInt();
		Seg[] seg = new Seg[N];
		int total = 0;
		for(int i = 0; i < N; i++){
			int l = nextInt();
			int r = nextInt();
			total += r - l + 1;
			seg[i] = new Seg(l, r);
		}
		
		Arrays.sort(seg);
		
		int length = seg[N - 1].r + 1 - seg[0].l;
		
		//System.out.println(total + " " + length);
		int build = length - total;
		if(length % K != 0){
			build += K - (length % K);
		}
		
		System.out.println(build % K);
		
	}

	
	
	
	
	
	
	
	
	
	
	//-----------------------------------------------------------
	public static void main(String[] args) {
		new A289().run();
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			tok = null;
			solve();
			in.close();
		} catch (IOException e) {
			System.exit(0);
		}
	}

	public String nextToken() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	BufferedReader in;
	StringTokenizer tok;
}
