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*<sub class="lower-index">1</sub>; *r*<sub class="lower-index">1</sub>], [*l*<sub class="lower-index">2</sub>; *r*<sub class="lower-index">2</sub>], ..., [*l*<sub class="lower-index">*n*</sub>; *r*<sub class="lower-index">*n*</sub>]. 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*<sub class="lower-index">1</sub>; *r*<sub class="lower-index">1</sub>], [*l*<sub class="lower-index">2</sub>; *r*<sub class="lower-index">2</sub>], ..., [*l*<sub class="lower-index">*n*</sub>; *r*<sub class="lower-index">*n*</sub>] is the number of integers *x*, such that there is integer *j*, for which the following inequality holds, *l*<sub class="lower-index">*j*</sub> ≤ *x* ≤ *r*<sub class="lower-index">*j*</sub>.

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<sup class="upper-index">5</sup>). Each of the following *n* lines contain a segment as a pair of integers *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> ( - 10<sup class="upper-index">5</sup> ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>), 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*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*j*</sub>) &lt; *max*(*l*<sub class="lower-index">*i*</sub>, *l*<sub class="lower-index">*j*</sub>).
#!/usr/bin/env python

def main():
    MAX = 10 ** 5 + 1
    n, k = map(int, input().split())
    segments = []
    _sum = 0
    for _ in range(n):
        li, ri = map(int, input().split())
        segments.append((li, ri))
        _sum += ri - li + 1

    if _sum % k == 0:
        print(0)
        return
    segments.sort()
    segments = [(-MAX, - MAX)] + segments
    segments.append((MAX, MAX))

    ans = 0
    for i in range(1, len(segments)-1):
        prv, cur, nxt = segments[i-1], segments[i], segments[i+1]

        if cur[0] - 1 != prv[1]:
            _sum += 1
            ans += 1
        elif cur[1] + 1 != nxt[0]:
            _sum += 1
            segments[i] = (segments[i][0], segments[i][1] + 1)
            ans += 1
        if _sum % k == 0:
            print(ans)
            break
    else:
        print('ops')

    
            

    

if __name__ == '__main__':
    main()
