시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 40 12 11 36.667%

문제

ACME Inc. 는 최근 생산성을 높이기 위해서 공장을 개편했다. 공장은 p개의 독립적이고 동일한 생산 라인으로 구성되어 있으며, 각각의 생산 라인에는 몇 명의 노동자가 배정된다.

실제로 모든 일은 기계가 다 하기 때문에 노동자가 몇명이 붙어있건 생산율은 동일하다. 한편, 안전 규정상 생산 라인은 모든 노동자가 근무 중일 때만 작동할 수 있다. 이 말을 요약하자면, 어떠한 생산 라인의 생산성은 라인에 할당된 모든 노동자가 근무하는 시간과 동일하다고 할 수 있다. 또한, 노동자들을 뿌듯하게 하기 위해서 각 생산 라인의 생산성은 항상 0 초과여야 한다.

한편, 노동법상 ACME는 한명의 노동자도 해고할 수 없다 - 즉, 모든 n명의 노동자들을 생산 라인에 배정해야 한다. 이 때 그들의 새 공장에서 가능한 최대의 생산성은 얼마인가?

입력

입력은 다음과 같이 구성된다.

  • 첫번째 줄에 n, p가 주어진다 (1 ≤ p ≤ n ≤ 200). 노동자의 수와 생산 라인의 수를 뜻한다.
  • 이후 n개의 줄에 a, b가 주어진다 (0 ≤ a < b ≤ 100 000). 노동자는 시간 a에 출근하고 시간 b에 퇴근한다.

올바른 배정이 최소 하나 존재함이 보장된다.

출력

공장의 최대 생산성을 출력하라.

예제 입력 1

4 2
1 3
1 5
4 6
2 7

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjExNjY3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGRkXHVjMGIwXHVjMTMxIFx1ZDVhNVx1YzBjMSIsImRlc2NyaXB0aW9uIjoiPHA+QUNNRSBJbmMuIFx1YjI5NCBcdWNkNWNcdWFkZmMgXHVjMGRkXHVjMGIwXHVjMTMxXHVjNzQ0IFx1YjE5Mlx1Yzc3NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhY2Y1XHVjN2E1XHVjNzQ0IFx1YWMxY1x1ZDNiOFx1ZDU4OFx1YjJlNC4gXHVhY2Y1XHVjN2E1XHVjNzQwIHBcdWFjMWNcdWM3NTggXHViM2M1XHViOWJkXHVjODAxXHVjNzc0XHVhY2UwIFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWMwZGRcdWMwYjAgXHViNzdjXHVjNzc4XHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMwZGRcdWMwYjAgXHViNzdjXHVjNzc4XHVjNWQwXHViMjk0IFx1YmE4NyBcdWJhODVcdWM3NTggXHViMTc4XHViM2Q5XHVjNzkwXHVhYzAwIFx1YmMzMFx1YzgxNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmU0XHVjODFjXHViODVjIFx1YmFhOFx1YjRlMCBcdWM3N2NcdWM3NDAgXHVhZTMwXHVhY2M0XHVhYzAwIFx1YjJlNCBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjE3OFx1YjNkOVx1Yzc5MFx1YWMwMCBcdWJhODdcdWJhODVcdWM3NzQgXHViZDk5XHVjNWI0XHVjNzg4XHVhYzc0IFx1YzBkZFx1YzBiMFx1YzcyOFx1Yzc0MCBcdWIzZDlcdWM3N2NcdWQ1NThcdWIyZTQuIFx1ZDU1Y1x1ZDNiOCwgXHVjNTQ4XHVjODA0IFx1YWRkY1x1YzgxNVx1YzBjMSBcdWMwZGRcdWMwYjAgXHViNzdjXHVjNzc4XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWIxNzhcdWIzZDlcdWM3OTBcdWFjMDAgXHVhZGZjXHViYjM0IFx1YzkxMVx1Yzc3YyBcdWI1NGNcdWI5Y2MgXHVjNzkxXHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7XHVjNzc0IFx1YjlkMFx1Yzc0NCBcdWM2OTRcdWM1N2RcdWQ1NThcdWM3OTBcdWJhNzQsIFx1YzViNFx1YjVhMFx1ZDU1YyBcdWMwZGRcdWMwYjAgXHViNzdjXHVjNzc4XHVjNzU4IFx1YzBkZFx1YzBiMFx1YzEzMVx1Yzc0MCBcdWI3N2NcdWM3NzhcdWM1ZDAgXHVkNTYwXHViMmY5XHViNDFjIFx1YmFhOFx1YjRlMCBcdWIxNzhcdWIzZDlcdWM3OTBcdWFjMDAgXHVhZGZjXHViYjM0XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWIzZDlcdWM3N2NcdWQ1NThcdWIyZTRcdWFjZTAgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHViMTc4XHViM2Q5XHVjNzkwXHViNGU0XHVjNzQ0IFx1YmZjY1x1YjRlZlx1ZDU1OFx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YWMwMSBcdWMwZGRcdWMwYjAgXHViNzdjXHVjNzc4XHVjNzU4IFx1YzBkZFx1YzBiMFx1YzEzMVx1Yzc0MCBcdWQ1NmRcdWMwYzEgMCBcdWNkMDhcdWFjZmNcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NWNcdWQzYjgsIFx1YjE3OFx1YjNkOVx1YmM5NVx1YzBjMSBBQ01FXHViMjk0IFx1ZDU1Y1x1YmE4NVx1Yzc1OCBcdWIxNzhcdWIzZDlcdWM3OTBcdWIzYzQgXHVkNTc0XHVhY2UwXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQgLSBcdWM5ODksIFx1YmFhOFx1YjRlMCBuXHViYTg1XHVjNzU4IFx1YjE3OFx1YjNkOVx1Yzc5MFx1YjRlNFx1Yzc0NCBcdWMwZGRcdWMwYjAgXHViNzdjXHVjNzc4XHVjNWQwIFx1YmMzMFx1YzgxNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMgXHVhZGY4XHViNGU0XHVjNzU4IFx1YzBjOCBcdWFjZjVcdWM3YTVcdWM1ZDBcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWMwZGRcdWMwYjBcdWMxMzFcdWM3NDAgXHVjNWJjXHViOWM4XHVjNzc4XHVhYzAwPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgbiwgcFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgKDEgJmxlOyBwICZsZTsgbiAmbGU7IDIwMCkuIFx1YjE3OFx1YjNkOVx1Yzc5MFx1Yzc1OCBcdWMyMThcdWM2NDAgXHVjMGRkXHVjMGIwIFx1Yjc3Y1x1Yzc3OFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViNzNiXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWQ2YzQgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgYSwgYlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgKDAgJmxlOyBhICZsdDsgYiAmbGU7IDEwMCAwMDApLiBcdWIxNzhcdWIzZDlcdWM3OTBcdWIyOTQgXHVjMmRjXHVhYzA0IGFcdWM1ZDAgXHVjZDljXHVhZGZjXHVkNTU4XHVhY2UwIFx1YzJkY1x1YWMwNCBiXHVjNWQwIFx1ZDFmNFx1YWRmY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM2MmNcdWJjMTRcdWI5NzggXHViYzMwXHVjODE1XHVjNzc0IFx1Y2Q1Y1x1YzE4YyBcdWQ1NThcdWIwOTggXHVjODc0XHVjN2FjXHVkNTY4XHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjZjVcdWM3YTVcdWM3NTggXHVjZDVjXHViMzAwIFx1YzBkZFx1YzBiMFx1YzEzMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE2NjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCZXR0ZXIgUHJvZHVjdGl2aXR5IiwiZGVzY3JpcHRpb24iOiI8cD5BQ01FIEluYy4gaXMgcmVvcmdhbml6aW5nIHRoZWlyIGZhY3RvcnksIGluIG9yZGVyIHRvIG1heGltaXplIHRoZWlyIHByb2R1Y3Rpdml0eSBvZiB1c2VsZXNzIHRyaW5rZXRzLiBUaGUgbmV3IGZhY3RvcnkgZGVzaWduIGNvbnNpc3RzIG9mIHAgaW5kZXBlbmRlbnQgYW5kIGlkZW50aWNhbCBwcm9kdWN0aW9uIGxpbmVzLiBFYWNoIHByb2R1Y3Rpb24gbGluZSBjYW4gYmUgYXNzaWduZWQgc29tZSBudW1iZXIgb2Ygd29ya2Vycy48XC9wPlxyXG5cclxuPHA+VGhlIGFjdHVhbCB3b3JrIGlzIG9mIGNvdXJzZSBhbGwgZG9uZSBieSBtYWNoaW5lcywgc28gdGhlIHByb2R1Y3Rpb24gcmF0ZSBvZiBhIHByb2R1Y3Rpb24gbGluZSBpcyBpbmRlcGVuZGVudCBvZiB0aGUgYWN0dWFsIG51bWJlciBvZiB3b3JrZXJzIGFzc2lnbmVkIHRvIGl0LiBIb3dldmVyLCB0aGUgd29ya2VycyB3b3JrIGluIHNoaWZ0cywgYW5kIGR1ZSB0byBsb2NhbCBzYWZldHkgcmVndWxhdGlvbnMsIGEgcHJvZHVjdGlvbiBsaW5lIGNhbiBvbmx5IGJlIGFjdGl2ZSB3aGlsZSBhbGwgb2YgaXRzIHdvcmtlcnMgYXJlIHByZXNlbnQgKGFueSB3b3JrZXIgd2hvIGFycml2ZXMgYmVmb3JlIHRoZSBsYXN0IHBlcnNvbiB0byBhcnJpdmUsIG9yIGxlYXZlcyBhZnRlciB0aGUgZmlyc3QgcGVyc29uIGxlYXZlcywgd2lsbCBiZSBzcGVuZGluZyB0aGUgaW5hY3RpdmUgdGltZSBoYXZpbmcgYSBjb2ZmZWUgYnJlYWspLiBJbiBvdGhlciB3b3JkcywgdGhlIHByb2R1Y3Rpdml0eSBvZiBhIHByb2R1Y3Rpb24gbGluZSBlcXVhbHMgdGhlIGxlbmd0aCBvZiB0aGUgdGltZXNwYW4gZHVyaW5nIHdoaWNoIGFsbCBvZiB0aGUgd29ya2VycyBhc3NpZ25lZCB0byB0aGlzIHByb2R1Y3Rpb24gbGluZSBhcmUgcHJlc2VudC4gQ3J1Y2lhbGx5LCB0aGUgcHJvZHVjdGl2aXR5IG9mIGVhY2ggbGluZSBtdXN0IGJlIHBvc2l0aXZlIChpLmUuLCB0aGUgbGFzdCB3b3JrZXIgdG8gYXJyaXZlIGZvciBhIGxpbmUgbXVzdCBhcnJpdmUgc3RyaWN0bHkgYmVmb3JlIHRoZSBmaXJzdCB3b3JrZXIgZm9yIHRoYXQgbGluZSBsZWF2ZXMpLCBzaW5jZSBvdGhlcndpc2UgdGhlIHdvcmtlcnMgZmVlbCB0aGF0IHRoZWlyIGpvYnMgYXJlIG1lYW5pbmdsZXNzLjxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCBkdWUgdG8gc29tZSBwZXNreSBsYWJvciBsYXdzLCBBQ01FIGFyZSBub3QgYWxsb3dlZCB0byBmaXJlIGFueSBvZiB0aGVpciB3b3JrZXJzLCB3aGljaCBtZWFucyB0aGF0IGVhY2ggb2YgdGhlaXIgbiB3b3JrZXJzIG11c3QgYmUgYXNzaWduZWQgdG8gc29tZSBwcm9kdWN0aW9uIGxpbmUsIGV2ZW4gdGhvdWdoIHRoaXMgbWF5IGFjdHVhbGx5IGRlY3JlYXNlIHRoZSBvdmVyYWxsIHByb2R1Y3Rpdml0eSBvZiB0aGUgZmFjdG9yeS48XC9wPlxyXG5cclxuPHA+QWxsIHRoZXNlIHJ1bGVzIGFuZCByZWd1bGF0aW9ucyBhcmUgbWFraW5nIGEgaGVhZGFjaGUgZm9yIEFDTUUgbWFuYWdlbWVudC4gQ2FuIHlvdSBoZWxwIHRoZW0gZmlndXJlIG91dCB0aGUgbWF4aW11bSBwb3NzaWJsZSB0b3RhbCBwcm9kdWN0aXZpdHkgKHN1bSBvZiBwcm9kdWN0aXZpdGllcyBvZiB0aGUgcCBwcm9kdWN0aW9uIGxpbmVzKSBvZiB0aGVpciBuZXcgZmFjdG9yeT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyBuIGFuZCBwICgxICZsZTsgcCAmbGU7IG4gJmxlOyAyMDApLCB0aGUgbnVtYmVyIG9mIGVtcGxveWVlcyBhbmQgdGhlIG51bWJlciBvZiBwcm9kdWN0aW9uIGxpbmVzOzxcL2xpPlxyXG5cdDxsaT5uIGxpbmVzIGVhY2ggY29udGFpbmluZyB0d28gaW50ZWdlcnMgYSBhbmQgYiAoMCAmbGU7IGEgJmx0OyBiICZsZTsgMTAwIDAwMCksIHJlcHJlc2VudGluZyBhIHdvcmtlciB0aGF0IGFycml2ZXMgYXQgdGltZSBhIGFuZCBsZWF2ZXMgYXQgdGltZSBiLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIHRoYXQgdGhlcmUgZXhpc3RzIGF0IGxlYXN0IG9uZSB2YWxpZCBhc3NpZ25tZW50IG9mIHdvcmtlcnMgdG8gcHJvZHVjdGlvbiBsaW5lcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1heGltdW0gcHJvZHVjdGl2aXR5IGxldmVsIHBvc3NpYmxlIGZvciB0aGUgZmFjdG9yeS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=