시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 50 16 16 47.059%

문제

총 N개의 역을 지나가는 기차가 있다. (첫 역과 마지막 역도 포함한다)

기차가 첫 역을 출발할 때와 마지막 역에 도착할 때, 탑승하고 있는 승객은 아무도 없다. 각 역에서 기차를 타는 승객의 수와 기차에서 내리는 승객의 수는 입력으로 주어진다.

각 승객은 기차를 타고 역 몇 개를 지난 뒤에 지하철에서 내리고, 같은 열차를 두 번 이상 타지 않는다.

이 기차에는 기차표를 검사하는 직원이 타고 있다. 이 직원은 기차가 첫 번째 역에서 두 번째 역으로 가는 동안 기차를 타고 있는 모든 승객의 기차표를 검사한다. 그 다음에는 기차가 역 K개를 지날 때마다 표를 검사한다. (일반화 하면 a*K+1 번째 역에서 a*K+2 번째 역으로 가는 동안 검사한다) 따라서, 기차를 타고 있는 동안 기차표를 한 번도 검사받지 않는 승객이 있을 수도 있다.

이 때, 기차표를 한 번도 검사받지 않는 승객 수의 최소값과 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (2 ≤ N ≤ 1000, 1 ≤ K ≤ 1000)

다음 N개 줄에는 각 역에서 기차에서 내리는 승객의 수와 기차를 타는 승객의 수가 공백으로 구분되어져서 주어진다. (기차가 지나가는 역을 순서대로 주어진다) 모든 숫자는 0보다 크거나 같고, 1000보다 크지 않다.

출력

첫째 줄에 기차표를 한 번도 검사받지 않는 승객 수의 최소값과 최대값을 공백으로 구분해서 출력한다.

예제 입력 1

6 2
0 10
5 3
6 4
2 8
8 1
5 0

예제 출력 1

5 11
W3sicHJvYmxlbV9pZCI6IjMxNjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlMzBcdWNjMjhcdWQ0NWMgXHVhYzgwXHVjMGFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWM1ZWRcdWM3NDQgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0IFx1YWUzMFx1Y2MyOFx1YWMwMCBcdWM3ODhcdWIyZTQuIChcdWNjYWIgXHVjNWVkXHVhY2ZjIFx1YjljOFx1YzljMFx1YjljOSBcdWM1ZWRcdWIzYzQgXHVkM2VjXHVkNTY4XHVkNTVjXHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWFlMzBcdWNjMjhcdWFjMDAgXHVjY2FiIFx1YzVlZFx1Yzc0NCBcdWNkOWNcdWJjMWNcdWQ1NjAgXHViNTRjXHVjNjQwIFx1YjljOFx1YzljMFx1YjljOSBcdWM1ZWRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTYwIFx1YjU0YywgXHVkMGQxXHVjMmI5XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWMyYjlcdWFjMWRcdWM3NDAgXHVjNTQ0XHViYjM0XHViM2M0IFx1YzVjNlx1YjJlNC4gXHVhYzAxIFx1YzVlZFx1YzVkMFx1YzExYyBcdWFlMzBcdWNjMjhcdWI5N2MgXHVkMGMwXHViMjk0IFx1YzJiOVx1YWMxZFx1Yzc1OCBcdWMyMThcdWM2NDAgXHVhZTMwXHVjYzI4XHVjNWQwXHVjMTFjIFx1YjBiNFx1YjlhY1x1YjI5NCBcdWMyYjlcdWFjMWRcdWM3NTggXHVjMjE4XHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWMyYjlcdWFjMWRcdWM3NDAgXHVhZTMwXHVjYzI4XHViOTdjIFx1ZDBjMFx1YWNlMCBcdWM1ZWQgXHViYTg3IFx1YWMxY1x1Yjk3YyBcdWM5YzBcdWIwOWMgXHViNGE0XHVjNWQwIFx1YzljMFx1ZDU1OFx1Y2NhMFx1YzVkMFx1YzExYyBcdWIwYjRcdWI5YWNcdWFjZTAsIFx1YWMxOVx1Yzc0MCBcdWM1ZjRcdWNjMjhcdWI5N2MgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVkMGMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YWUzMFx1Y2MyOFx1YzVkMFx1YjI5NCBcdWFlMzBcdWNjMjhcdWQ0NWNcdWI5N2MgXHVhYzgwXHVjMGFjXHVkNTU4XHViMjk0IFx1YzljMVx1YzZkMFx1Yzc3NCBcdWQwYzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjOWMxXHVjNmQwXHVjNzQwIFx1YWUzMFx1Y2MyOFx1YWMwMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzVlZFx1YzVkMFx1YzExYyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzVlZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHViM2Q5XHVjNTQ4IFx1YWUzMFx1Y2MyOFx1Yjk3YyBcdWQwYzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyYjlcdWFjMWRcdWM3NTggXHVhZTMwXHVjYzI4XHVkNDVjXHViOTdjIFx1YWM4MFx1YzBhY1x1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWFlMzBcdWNjMjhcdWFjMDAgXHVjNWVkIEtcdWFjMWNcdWI5N2MgXHVjOWMwXHViMGEwIFx1YjU0Y1x1YjljOFx1YjJlNCBcdWQ0NWNcdWI5N2MgXHVhYzgwXHVjMGFjXHVkNTVjXHViMmU0LiAoXHVjNzdjXHViYzE4XHVkNjU0IFx1ZDU1OFx1YmE3NCBhKksrMSBcdWJjODhcdWM5ZjggXHVjNWVkXHVjNWQwXHVjMTFjIGEqSysyIFx1YmM4OFx1YzlmOCBcdWM1ZWRcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YjNkOVx1YzU0OCBcdWFjODBcdWMwYWNcdWQ1NWNcdWIyZTQpIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhZTMwXHVjYzI4XHViOTdjIFx1ZDBjMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViM2Q5XHVjNTQ4IFx1YWUzMFx1Y2MyOFx1ZDQ1YzxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWI5N2MgXHVkNTVjIFx1YmM4OFx1YjNjNCBcdWFjODBcdWMwYWNcdWJjMWJcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzJiOVx1YWMxZFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9zcGFuPjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViNTRjLCBcdWFlMzBcdWNjMjhcdWQ0NWNcdWI5N2MgXHVkNTVjIFx1YmM4OFx1YjNjNCBcdWFjODBcdWMwYWNcdWJjMWJcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzJiOVx1YWMxZCBcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVhY2ZjIFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwMCwgMSAmbGU7IEsgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzVlZFx1YzVkMFx1YzExYyBcdWFlMzBcdWNjMjhcdWM1ZDBcdWMxMWMgXHViMGI0XHViOWFjXHViMjk0IFx1YzJiOVx1YWMxZFx1Yzc1OCBcdWMyMThcdWM2NDAgXHVhZTMwXHVjYzI4XHViOTdjIFx1ZDBjMFx1YjI5NCBcdWMyYjlcdWFjMWRcdWM3NTggXHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzhcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHVhZTMwXHVjYzI4XHVhYzAwIFx1YzljMFx1YjA5OFx1YWMwMFx1YjI5NCBcdWM1ZWRcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCkgXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwMDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWUzMFx1Y2MyOFx1ZDQ1Y1x1Yjk3YyBcdWQ1NWMgXHViYzg4XHViM2M0IFx1YWM4MFx1YzBhY1x1YmMxYlx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMmI5XHVhYzFkIFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWFjZmMgXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzRcdWMxMWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxNjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJrb250cm9sYSIsImRlc2NyaXB0aW9uIjoiPHA+QSB0cmFpbiBpcyBvcGVyYXRpbmcgb24gYSBsaW5lIHRoYXQgY29uc2lzdHMgb2YgTiBzdG9wcyAoaW5jbHVkaW5nIHRoZSBmaXJzdCBhbmQgbGFzdCBzdG9wcykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0cmFpbiBpcyBlbXB0eSBpbiB0aGUgYmVnaW5uaW5nIGFuZCBpbiB0aGUgZW5kLCBhbmQgZm9yIGVhY2ggc3RvcCB3ZSBrbm93IHRoZSBudW1iZXIgb2YgcGFzc2VuZ2VycyB0aGF0IGxlYXZlIHRoZSB0cmFpbiBhbmQgdGhlIG51bWJlciBvZiBwYXNzZW5nZXJzIHRoYXQgZW50ZXIgdGhlIHRyYWluLiBFYWNoIHBhc3NlbmdlciBpcyB0cmF2ZWxpbmcgZm9yIHNvbWUgbnVtYmVyIG9mIHN0b3BzIGFuZCB0aGUgc2FtZSBwYXNzZW5nZXIgbmV2ZXIgYm9hcmRzIHRoZSBzYW1lIHRyYWluIG1vcmUgdGhhbiBvbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVyZSBpcyBhIHRpY2tldCBpbnNwZWN0b3IgaW4gdGhlIHRyYWluLiBIZSB3YWxrcyB0aHJvdWdoIHRoZSBlbnRpcmUgdHJhaW4gYmV0d2VlbiB0aGUgZmlyc3QgYW5kIHNlY29uZCBzdG9wcyBhbmQgaW5zcGVjdHMgdGhlIHRpY2tldHMgb2YgYWxsIHBhc3NlbmdlcnMgY3VycmVudGx5IGFib2FyZC4gQWZ0ZXIgdGhhdCwgdGhlIGluc3BlY3RvciBpbnNwZWN0cyB0aWNrZXRzIGFnYWluIGFmdGVyIGV2ZXJ5IEsgc3RvcHMgKGhlbmNlIGhlIGluc3BlY3RzIHRoZSB0aWNrZXQgYmV0d2VlbiBzdG9wcyBhKksrMSBhbmQgYSpLKzIgZm9yIGVhY2ggaW50ZWdlciBhKS4gSXQgaXMgdGhlcmVmb3JlIHBvc3NpYmxlIHRoYXQgc29tZSBwYXNzZW5nZXJzIGVudGVyIGFuZCBsZWF2ZSB0aGUgdHJhaW4gd2l0aCB0aGVpciB0aWNrZXRzIG5ldmVyIGluc3BlY3RlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIG1pbmltdW0gYW5kIG1heGltdW0gcG9zc2libGUgbnVtYmVyIG9mIHN1Y2ggcGFzc2VuZ2Vycy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBLLCAyICZsZTsgTiAmbGU7IDEwMDAsIDEgJmxlOyBLICZsZTsgMTAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAmbmRhc2g7IHRoZSBudW1iZXIgb2YgcGFzc2VuZ2VycyB0aGF0IGxlYXZlIGFuZCB0aGUgbnVtYmVyIG9mIHBhc3NlbmdlcnMgdGhhdCBlbnRlciBvbiB0aGF0IHBhcnRpY3VsYXIgc3RvcCAoZnJvbSB0aGUgZmlyc3QgdG8gdGhlIGxhc3Qgc3RvcCkuIFRoZXNlIG51bWJlcnMgd2lsbCBiZSBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gMCBhbmQgbm8gZ3JlYXRlciB0aGFuIDEwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHR3byBpbnRlZ2VycyAmbmRhc2g7IHRoZSBtaW5pbXVtIGFuZCBtYXhpbXVtIG51bWJlcnMgZnJvbSB0aGUgdGFzayBkZXNjcmlwdGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=