289A.md (1713B)
1 Source: https://codeforces.com/problemset/problem/289/A 2 3 A. Polo the Penguin and Segments 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Little penguin Polo adores integer segments, that is, pairs of integers [*l*; *r*] (*l* ≤ *r*). 22 23 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]. 24 25 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*. 26 27 Find the minimum number of moves needed to make the value of the set of Polo's segments divisible by *k*. 28 29 Input 30 31 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 *l**i* and *r**i* ( - 105 ≤ *l**i* ≤ *r**i* ≤ 105), separated by a space. 32 33 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*). 34 35 Output 36 37 In a single line print a single integer — the answer to the problem. 38 39 Examples 40 41 Input 42 43 ``` 44 2 3 45 1 2 46 3 4 47 ``` 48 49 Output 50 51 ``` 52 2 53 ``` 54 55 Input 56 57 ``` 58 3 7 59 1 2 60 3 3 61 4 7 62 ``` 63 64 Output 65 66 ``` 67 0 68 ```