시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsIFx1YWUzMFx1Y2MyOFx1ZDQ1Y1x1Yjk3YyBcdWQ1NWMgXHViYzg4XHViM2M0IFx1YWM4MFx1YzBhY1x1YmMxYlx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMmI5XHVhYzFkIFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWFjZmMgXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAwLCAxICZsZTsgSyAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjNWVkXHVjNWQwXHVjMTFjIFx1YWUzMFx1Y2MyOFx1YzVkMFx1YzExYyBcdWIwYjRcdWI5YWNcdWIyOTQgXHVjMmI5XHVhYzFkXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWFlMzBcdWNjMjhcdWI5N2MgXHVkMGMwXHViMjk0IFx1YzJiOVx1YWMxZFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChcdWFlMzBcdWNjMjhcdWFjMDAgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0IFx1YzVlZFx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KSBcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZTMwXHVjYzI4XHVkNDVjXHViOTdjIFx1ZDU1YyBcdWJjODhcdWIzYzQgXHVhYzgwXHVjMGFjXHViYzFiXHVjOWMwIFx1YzU0YVx1YjI5NCBcdWMyYjlcdWFjMWQgXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1YWNmYyBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE2NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6ImtvbnRyb2xhIiwiZGVzY3JpcHRpb24iOiI8cD5BIHRyYWluIGlzIG9wZXJhdGluZyBvbiBhIGxpbmUgdGhhdCBjb25zaXN0cyBvZiBOIHN0b3BzIChpbmNsdWRpbmcgdGhlIGZpcnN0IGFuZCBsYXN0IHN0b3BzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRyYWluIGlzIGVtcHR5IGluIHRoZSBiZWdpbm5pbmcgYW5kIGluIHRoZSBlbmQsIGFuZCBmb3IgZWFjaCBzdG9wIHdlIGtub3cgdGhlIG51bWJlciBvZiBwYXNzZW5nZXJzIHRoYXQgbGVhdmUgdGhlIHRyYWluIGFuZCB0aGUgbnVtYmVyIG9mIHBhc3NlbmdlcnMgdGhhdCBlbnRlciB0aGUgdHJhaW4uIEVhY2ggcGFzc2VuZ2VyIGlzIHRyYXZlbGluZyBmb3Igc29tZSBudW1iZXIgb2Ygc3RvcHMgYW5kIHRoZSBzYW1lIHBhc3NlbmdlciBuZXZlciBib2FyZHMgdGhlIHNhbWUgdHJhaW4gbW9yZSB0aGFuIG9uY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGEgdGlja2V0IGluc3BlY3RvciBpbiB0aGUgdHJhaW4uIEhlIHdhbGtzIHRocm91Z2ggdGhlIGVudGlyZSB0cmFpbiBiZXR3ZWVuIHRoZSBmaXJzdCBhbmQgc2Vjb25kIHN0b3BzIGFuZCBpbnNwZWN0cyB0aGUgdGlja2V0cyBvZiBhbGwgcGFzc2VuZ2VycyBjdXJyZW50bHkgYWJvYXJkLiBBZnRlciB0aGF0LCB0aGUgaW5zcGVjdG9yIGluc3BlY3RzIHRpY2tldHMgYWdhaW4gYWZ0ZXIgZXZlcnkgSyBzdG9wcyAoaGVuY2UgaGUgaW5zcGVjdHMgdGhlIHRpY2tldCBiZXR3ZWVuIHN0b3BzIGEqSysxIGFuZCBhKksrMiBmb3IgZWFjaCBpbnRlZ2VyIGEpLiBJdCBpcyB0aGVyZWZvcmUgcG9zc2libGUgdGhhdCBzb21lIHBhc3NlbmdlcnMgZW50ZXIgYW5kIGxlYXZlIHRoZSB0cmFpbiB3aXRoIHRoZWlyIHRpY2tldHMgbmV2ZXIgaW5zcGVjdGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBmaW5kcyB0aGUgbWluaW11bSBhbmQgbWF4aW11bSBwb3NzaWJsZSBudW1iZXIgb2Ygc3VjaCBwYXNzZW5nZXJzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEssIDIgJmxlOyBOICZsZTsgMTAwMCwgMSAmbGU7IEsgJmxlOyAxMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzICZuZGFzaDsgdGhlIG51bWJlciBvZiBwYXNzZW5nZXJzIHRoYXQgbGVhdmUgYW5kIHRoZSBudW1iZXIgb2YgcGFzc2VuZ2VycyB0aGF0IGVudGVyIG9uIHRoYXQgcGFydGljdWxhciBzdG9wIChmcm9tIHRoZSBmaXJzdCB0byB0aGUgbGFzdCBzdG9wKS4gVGhlc2UgbnVtYmVycyB3aWxsIGJlIGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byAwIGFuZCBubyBncmVhdGVyIHRoYW4gMTAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdHdvIGludGVnZXJzICZuZGFzaDsgdGhlIG1pbmltdW0gYW5kIG1heGltdW0gbnVtYmVycyBmcm9tIHRoZSB0YXNrIGRlc2NyaXB0aW9uLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==