시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWQ1NWNcdWQzYjgsIFx1YjE3OFx1YjNkOVx1YmM5NVx1YzBjMSBBQ01FXHViMjk0IFx1ZDU1YyBcdWJhODVcdWM3NTggXHViMTc4XHViM2Q5XHVjNzkwXHViM2M0IFx1ZDU3NFx1YWNlMFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0IC0gXHVjOTg5LCBcdWJhYThcdWI0ZTAgblx1YmE4NVx1Yzc1OCBcdWIxNzhcdWIzZDlcdWM3OTBcdWI0ZTRcdWM3NDQgXHVjMGRkXHVjMGIwIFx1Yjc3Y1x1Yzc3OFx1YzVkMCBcdWJjMzBcdWM4MTVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMgXHVhZGY4XHViNGU0XHVjNzU4IFx1YzBjOCBcdWFjZjVcdWM3YTVcdWM1ZDBcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWMwZGRcdWMwYjBcdWMxMzFcdWM3NDAgXHVjNWJjXHViOWM4XHVjNzc4XHVhYzAwPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIG4sIHBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsgcCAmbGU7IG4gJmxlOyAyMDApLiBcdWIxNzhcdWIzZDlcdWM3OTBcdWM3NTggXHVjMjE4XHVjNjQwIFx1YzBkZFx1YzBiMCBcdWI3N2NcdWM3NzhcdWM3NTggXHVjMjE4XHViOTdjIFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc0XHVkNmM0IG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIGEsIGJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgwICZsZTsgYSAmbHQ7IGIgJmxlOyAxMDAgMDAwKS4gXHViMTc4XHViM2Q5XHVjNzkwXHViMjk0IFx1YzJkY1x1YWMwNCBhXHVjNWQwIFx1Y2Q5Y1x1YWRmY1x1ZDU1OFx1YWNlMCBcdWMyZGNcdWFjMDQgYlx1YzVkMCBcdWQxZjRcdWFkZmNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjJjXHViYzE0XHViOTc4IFx1YmMzMFx1YzgxNVx1Yzc3NCBcdWNkNWNcdWMxOGMgXHVkNTU4XHViMDk4IFx1Yzg3NFx1YzdhY1x1ZDU2OFx1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhY2Y1XHVjN2E1XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWMwZGRcdWMwYjBcdWMxMzFcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExNjY3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmV0dGVyIFByb2R1Y3Rpdml0eSIsImRlc2NyaXB0aW9uIjoiPHA+QUNNRSBJbmMuIGlzIHJlb3JnYW5pemluZyB0aGVpciBmYWN0b3J5LCBpbiBvcmRlciB0byBtYXhpbWl6ZSB0aGVpciBwcm9kdWN0aXZpdHkgb2YgdXNlbGVzcyB0cmlua2V0cy4gVGhlIG5ldyBmYWN0b3J5IGRlc2lnbiBjb25zaXN0cyBvZiBwIGluZGVwZW5kZW50IGFuZCBpZGVudGljYWwgcHJvZHVjdGlvbiBsaW5lcy4gRWFjaCBwcm9kdWN0aW9uIGxpbmUgY2FuIGJlIGFzc2lnbmVkIHNvbWUgbnVtYmVyIG9mIHdvcmtlcnMuPFwvcD5cclxuXHJcbjxwPlRoZSBhY3R1YWwgd29yayBpcyBvZiBjb3Vyc2UgYWxsIGRvbmUgYnkgbWFjaGluZXMsIHNvIHRoZSBwcm9kdWN0aW9uIHJhdGUgb2YgYSBwcm9kdWN0aW9uIGxpbmUgaXMgaW5kZXBlbmRlbnQgb2YgdGhlIGFjdHVhbCBudW1iZXIgb2Ygd29ya2VycyBhc3NpZ25lZCB0byBpdC4gSG93ZXZlciwgdGhlIHdvcmtlcnMgd29yayBpbiBzaGlmdHMsIGFuZCBkdWUgdG8gbG9jYWwgc2FmZXR5IHJlZ3VsYXRpb25zLCBhIHByb2R1Y3Rpb24gbGluZSBjYW4gb25seSBiZSBhY3RpdmUgd2hpbGUgYWxsIG9mIGl0cyB3b3JrZXJzIGFyZSBwcmVzZW50IChhbnkgd29ya2VyIHdobyBhcnJpdmVzIGJlZm9yZSB0aGUgbGFzdCBwZXJzb24gdG8gYXJyaXZlLCBvciBsZWF2ZXMgYWZ0ZXIgdGhlIGZpcnN0IHBlcnNvbiBsZWF2ZXMsIHdpbGwgYmUgc3BlbmRpbmcgdGhlIGluYWN0aXZlIHRpbWUgaGF2aW5nIGEgY29mZmVlIGJyZWFrKS4gSW4gb3RoZXIgd29yZHMsIHRoZSBwcm9kdWN0aXZpdHkgb2YgYSBwcm9kdWN0aW9uIGxpbmUgZXF1YWxzIHRoZSBsZW5ndGggb2YgdGhlIHRpbWVzcGFuIGR1cmluZyB3aGljaCBhbGwgb2YgdGhlIHdvcmtlcnMgYXNzaWduZWQgdG8gdGhpcyBwcm9kdWN0aW9uIGxpbmUgYXJlIHByZXNlbnQuIENydWNpYWxseSwgdGhlIHByb2R1Y3Rpdml0eSBvZiBlYWNoIGxpbmUgbXVzdCBiZSBwb3NpdGl2ZSAoaS5lLiwgdGhlIGxhc3Qgd29ya2VyIHRvIGFycml2ZSBmb3IgYSBsaW5lIG11c3QgYXJyaXZlIHN0cmljdGx5IGJlZm9yZSB0aGUgZmlyc3Qgd29ya2VyIGZvciB0aGF0IGxpbmUgbGVhdmVzKSwgc2luY2Ugb3RoZXJ3aXNlIHRoZSB3b3JrZXJzIGZlZWwgdGhhdCB0aGVpciBqb2JzIGFyZSBtZWFuaW5nbGVzcy48XC9wPlxyXG5cclxuPHA+VW5mb3J0dW5hdGVseSwgZHVlIHRvIHNvbWUgcGVza3kgbGFib3IgbGF3cywgQUNNRSBhcmUgbm90IGFsbG93ZWQgdG8gZmlyZSBhbnkgb2YgdGhlaXIgd29ya2Vycywgd2hpY2ggbWVhbnMgdGhhdCBlYWNoIG9mIHRoZWlyIG4gd29ya2VycyBtdXN0IGJlIGFzc2lnbmVkIHRvIHNvbWUgcHJvZHVjdGlvbiBsaW5lLCBldmVuIHRob3VnaCB0aGlzIG1heSBhY3R1YWxseSBkZWNyZWFzZSB0aGUgb3ZlcmFsbCBwcm9kdWN0aXZpdHkgb2YgdGhlIGZhY3RvcnkuPFwvcD5cclxuXHJcbjxwPkFsbCB0aGVzZSBydWxlcyBhbmQgcmVndWxhdGlvbnMgYXJlIG1ha2luZyBhIGhlYWRhY2hlIGZvciBBQ01FIG1hbmFnZW1lbnQuIENhbiB5b3UgaGVscCB0aGVtIGZpZ3VyZSBvdXQgdGhlIG1heGltdW0gcG9zc2libGUgdG90YWwgcHJvZHVjdGl2aXR5IChzdW0gb2YgcHJvZHVjdGl2aXRpZXMgb2YgdGhlIHAgcHJvZHVjdGlvbiBsaW5lcykgb2YgdGhlaXIgbmV3IGZhY3Rvcnk/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2Y6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgbiBhbmQgcCAoMSAmbGU7IHAgJmxlOyBuICZsZTsgMjAwKSwgdGhlIG51bWJlciBvZiBlbXBsb3llZXMgYW5kIHRoZSBudW1iZXIgb2YgcHJvZHVjdGlvbiBsaW5lczs8XC9saT5cclxuXHQ8bGk+biBsaW5lcyBlYWNoIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIGEgYW5kIGIgKDAgJmxlOyBhICZsdDsgYiAmbGU7IDEwMCAwMDApLCByZXByZXNlbnRpbmcgYSB3b3JrZXIgdGhhdCBhcnJpdmVzIGF0IHRpbWUgYSBhbmQgbGVhdmVzIGF0IHRpbWUgYi48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGF0IHRoZXJlIGV4aXN0cyBhdCBsZWFzdCBvbmUgdmFsaWQgYXNzaWdubWVudCBvZiB3b3JrZXJzIHRvIHByb2R1Y3Rpb24gbGluZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtYXhpbXVtIHByb2R1Y3Rpdml0eSBsZXZlbCBwb3NzaWJsZSBmb3IgdGhlIGZhY3RvcnkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d