시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1415 548 425 38.151%

문제

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.

한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.

상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.

상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 109, 1 ≤ M ≤ 300,000, M ≤ N)

다음 M개 줄에는 구간 [1, 109]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.

출력

첫째 줄에 질투심의 최솟값을 출력한다.

예제 입력 1

5 2
7
4

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjI3OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWMxMWQgXHVjMGMxXHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWJjZjRcdWMxMWQgXHVhY2Y1XHVjN2E1XHVjNWQwXHVjMTFjIFx1YmNmNFx1YzExZCBcdWMwYzFcdWM3OTBcdWI5N2MgXHVjNzIwXHVjZTU4XHVjNmQwXHVjNWQwIFx1YWUzMFx1Yzk5ZFx1ZDU4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmNmNFx1YzExZFx1Yzc0MCBNXHVhYzAwXHVjOWMwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMGM5XHVjMGMxIFx1YzkxMSBcdWQ1NWMgXHVjMGM5XHVjMGMxXHVjNzc0XHViMmU0LiBcdWM2ZDBcdWM3YTUgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWJjZjRcdWMxMWRcdWM3NDQgTlx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViMDk4XHViMjA0XHVjNWI0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YmMxYlx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVkNTU5XHVjMGRkXHVjNzc0IFx1Yzc4OFx1YzViNFx1YjNjNCBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVkNTU5XHVjMGRkXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWFjMTlcdWM3NDAgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YmNmNFx1YzExZFx1YjljYyBcdWFjMDBcdWM4MzhcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDU1YyBcdWM1NDRcdWM3NzRcdWFjMDAgXHViMTA4XHViYjM0IFx1YjljZVx1Yzc0MCBcdWJjZjRcdWMxMWRcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzAwXHVhYzhjIFx1YjQxOFx1YmE3NCwgXHViMmU0XHViOTc4IFx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc3NCBcdWM5YzhcdWQyMmNcdWI5N2MgXHVkNTVjXHViMmU0LiBcdWM2ZDBcdWM3YTUgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1Yzc3NFx1YjdmMCBcdWM5YzhcdWQyMmNcdWMyZWNcdWM3NDQgXHVjMjE4XHVjZTU4XHVkNjU0XHVkNTU4XHViMjk0XHViMzcwIFx1YzEzMVx1YWNmNVx1ZDU4OFx1YjI5NFx1YjM3MCwgXHVjOWM4XHVkMjJjXHVjMmVjXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwNCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJjZjRcdWMxMWRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM2ZDBcdWM3YTUgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1YzljOFx1ZDIyY1x1YzJlY1x1Yzc3NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHVhYzhjIFx1YmNmNFx1YzExZFx1Yzc0NCBcdWIwOThcdWIyMDRcdWM1YjQgXHVjOGZjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVjNzkwXHVjNWQwIFx1YmU2OFx1YWMwNCBcdWJjZjRcdWMxMWRcdWM3NzQgNFx1YWMxYyAoUlJSUiksIFx1ZDMwY1x1Yjc4MCBcdWJjZjRcdWMxMWRcdWM3NzQgN1x1YWMxYyAoQkJCQkJCQikgXHVjNzg4XHVjNWM4XHVhY2UwLCBcdWM3NzQgXHViY2Y0XHVjMTFkXHVjNzQ0IDVcdWJhODVcdWM3NTggXHVjNTQ0XHVjNzc0XHViNGU0XHVjNWQwXHVhYzhjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4ZmNcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gUlIsIFJSLCBCQiwgQkIsIEJCQlx1Yjg1YyBcdWJjZjRcdWMxMWRcdWM3NDQgXHViMDk4XHViMjA0XHVjNWI0XHVjOGZjXHViYTc0IFx1YzljOFx1ZDIyY1x1YzJlY1x1Yzc0MCAzXHVjNzc0IFx1YjQxOFx1YWNlMCwgXHVjNzc0IFx1YWMxMlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjOGMgXHViMDk4XHViMjA0XHVjNWI0IFx1YzkwNCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWM3OTAgXHVjNTQ4XHVjNzU4IFx1YmNmNFx1YzExZCBcdWM4MTVcdWJjZjRcdWM2NDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM5YzhcdWQyMmNcdWMyZWNcdWM3NzQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YWM4YyBcdWJjZjRcdWMxMWRcdWM3NDQgXHViMDk4XHViMjA0XHVjNWI0XHVjOGZjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YzBjOVx1YzBjMVx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwPHN1cD45PFwvc3VwPiwgMSAmbGU7IE0gJmxlOyAzMDAsMDAwLCBNICZsZTsgTik8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWQ2Y1x1YWMwNCBbMSwgMTA8c3VwPjk8XC9zdXA+XVx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBLXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IEtcdWJjODggXHVjMGM5XHVjMGMxIFx1YmNmNFx1YzExZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5YzhcdWQyMmNcdWMyZWNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTEpVQk9NT1JBIiwiZGVzY3JpcHRpb24iOiI8cD5BIG1hcmJsZSBmYWN0b3J5IGhhcyBkb25hdGVkIGEgbGFyZ2UgYm94IG9mIG1hcmJsZXMgdG8gYSBraW5kZXJnYXJ0ZW4uIEVhY2ggbWFyYmxlIGhhcyBvbmUgb3V0IG9mIE0gZGlmZmVyZW50IGNvbG91cnMuIFRoZSBnb3Zlcm5lc3MgbmVlZHMgdG8gZGl2aWRlIGFsbCB0aGUgbWFyYmxlcyBiZXR3ZWVuIHRoZSBOIGNoaWxkcmVuIGluIGhlciBncm91cC4gSXQgaXMgYWNjZXB0YWJsZSBpZiBzb21lIGNoaWxkcmVuIGRvbiYjMzk7dCBnZXQgYW55IG1hcmJsZXMuIEhvd2V2ZXIsIG5vIGNoaWxkIHdhbnRzIG1hcmJsZXMgb2YgZGlmZmVyZW50IGNvbG91cnMgJm5kYXNoOyBpbiBvdGhlciB3b3JkcywgYWxsIG1hcmJsZXMgdGhhdCBhIGNoaWxkIGdldHMgbmVlZCB0byBiZSB0aGUgc2FtZSBjb2xvdXIuPFwvcD5cclxuXHJcbjxwPlRoZSBnb3Zlcm5lc3MgYWxzbyBrbm93cyB0aGF0IGNoaWxkcmVuIHdpbGwgYmUgamVhbG91cyBpZiBhIGNoaWxkIGdldHMgdG9vIG1hbnkgbWFyYmxlcy4gQXMgYW4gYXBwcm94aW1hdGlvbiwgd2Ugd2lsbCBkZWZpbmUgdGhlIGVudnkgbGV2ZWwgaW4gdGhlIGdyb3VwIGFzIHRoZSBsYXJnZXN0IG51bWJlciBvZiBtYXJibGVzIGdpdmVuIHRvIG9uZSBjaGlsZC4gSGVscCB0aGUgZ292ZXJuZXNzIGRpdmlkZSB0aGUgbWFyYmxlcyBpbiBvcmRlciB0byBtaW5pbWl6ZSB0aGUgZW52eSBsZXZlbC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIHRoZSBib3ggY29udGFpbnMgNCByZWQgbWFyYmxlcyAoUlJSUikgYW5kIDcgYmx1ZSBtYXJibGVzIChCQkJCQkJCKSB3aGljaCB3ZSBoYXZlIHRvIGRpdmlkZSBiZXR3ZWVuIDUgY2hpbGRyZW4sIHdlIGNhbiBhY2hpZXZlIGFuIGVudnkgbGV2ZWwgb2YgMyBieSBkaXZpZGluZyB0aGUgbWFyYmxlcyBpbiB0aGUgZm9sbG93aW5nIHdheTogUlIsIFJSLCBCQiwgQkIsIEJCQi4gVGhpcyBpcyB0aGUgbG93ZXN0IGFjaGlldmFibGUgZW52eSBsZXZlbC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgTiAoMSAmbGU7IE4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLCB0aGUgbnVtYmVyIG9mIGNoaWxkcmVuLCBhbmQgTSAoMSAmbGU7IE0gJmxlOyAzMDAgMDAwLCBNICZsZTsgTiksIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGNvbG91cnMuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIGEgcG9zaXRpdmUgaW50ZWdlciBmcm9tIHRoZSBpbnRlcnZhbCBbMSwgMTA8c3VwPjk8XC9zdXA+XSwgd2l0aCB0aGUgaW50ZWdlciBpbiBsaW5lIEsgZGVub3RpbmcgdGhlIG51bWJlciBvZiBtYXJibGVzIHdpdGggY29sb3VyIEsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBtaW5pbXVtIHBvc3NpYmxlIGVudnkgbGV2ZWwuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==