시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1287 494 384 37.795%

문제

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 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
W3sicHJvYmxlbV9pZCI6IjI3OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWMxMWQgXHVjMGMxXHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWJjZjRcdWMxMWQgXHVhY2Y1XHVjN2E1XHVjNWQwXHVjMTFjIFx1YmNmNFx1YzExZCBcdWMwYzFcdWM3OTBcdWI5N2MgXHVjNzIwXHVjZTU4XHVjNmQwXHVjNWQwIFx1YWUzMFx1Yzk5ZFx1ZDU4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmNmNFx1YzExZFx1Yzc0MCBNXHVhYzAwXHVjOWMwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMGM5XHVjMGMxIFx1YzkxMSBcdWQ1NWMgXHVjMGM5XHVjMGMxXHVjNzc0XHViMmU0LiBcdWM2ZDBcdWM3YTUgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWJjZjRcdWMxMWRcdWM3NDQgTlx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViMDk4XHViMjA0XHVjNWI0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YmNmNFx1YzExZFx1Yzc0NCBcdWJjMWJcdWM5YzAgXHViYWJiXHVkNTU4XHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM3ODhcdWM1YjRcdWIzYzQgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVhYzE5XHVjNzQwIFx1YzBjOVx1YzBjMVx1Yzc1OCBcdWJjZjRcdWMxMWRcdWI5Y2MgXHVhYzAwXHVjODM4XHVhYzA0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQ1NWMgXHVjNTQ0XHVjNzc0XHVhYzAwIFx1YjEwOFx1YmIzNCBcdWI5Y2VcdWM3NDAgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YWM4YyBcdWI0MThcdWJhNzQsIFx1YjJlNFx1Yjk3OCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NzQgXHVjOWM4XHVkMjJjXHViOTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNmQwXHVjN2E1IFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWM3NzRcdWI3ZjAgXHVjOWM4XHVkMjJjXHVjMmVjXHVjNzQ0IFx1YzIxOFx1Y2U1OFx1ZDY1NFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWMxMzFcdWFjZjVcdWQ1ODhcdWIyOTRcdWIzNzAsIFx1YzljOFx1ZDIyY1x1YzJlY1x1Yzc0MCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YmNmNFx1YzExZFx1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDQgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViY2Y0XHVjMTFkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNmQwXHVjN2E1IFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWM5YzhcdWQyMmNcdWMyZWNcdWM3NzQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YWM4YyBcdWJjZjRcdWMxMWRcdWM3NDQgXHViMDk4XHViMjA0XHVjNWI0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1Yzc5MFx1YzVkMCBcdWJlNjhcdWFjMDQgXHViY2Y0XHVjMTFkXHVjNzc0IDRcdWFjMWMgKFJSUlIpLCBcdWQzMGNcdWI3ODAgXHViY2Y0XHVjMTFkXHVjNzc0IDdcdWFjMWMgKEJCQkJCQkIpIFx1Yzc4OFx1YzVjOFx1YWNlMCwgXHVjNzc0IFx1YmNmNFx1YzExZFx1Yzc0NCA1XHViYTg1XHVjNzU4IFx1YzU0NFx1Yzc3NFx1YjRlNFx1YzVkMFx1YWM4YyBcdWIwOThcdWIyMDRcdWM1YjQgXHVjOGZjXHViMjk0IFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWM3OTAuIFJSLCBSUiwgQkIsIEJCLCBCQkJcdWI4NWMgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YzViNFx1YzhmY1x1YmE3NCBcdWM5YzhcdWQyMmNcdWMyZWNcdWM3NDAgM1x1Yzc3NCBcdWI0MThcdWFjZTAsIFx1Yzc3NCBcdWFjMTJcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzhjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWM5MDQgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVjNzkwIFx1YzU0OFx1Yzc1OCBcdWJjZjRcdWMxMWQgXHVjODE1XHViY2Y0XHVjNjQwIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjOWM4XHVkMjJjXHVjMmVjXHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWFjOGMgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YzViNFx1YzhmY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWMwYzlcdWMwYzFcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDxzdXA+OTxcL3N1cD4sIDEgJmxlOyBNICZsZTsgMzAwLDAwMCwgTSAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkNmNcdWFjMDQgWzEsIDEwPHN1cD45PFwvc3VwPl1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gS1x1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIyYlx1Yzc5MFx1YjI5NCBLXHViYzg4IFx1YzBjOVx1YzBjMSBcdWJjZjRcdWMxMWRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWM4XHVkMjJjXHVjMmVjXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc5MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxKVUJPTU9SQSIsImRlc2NyaXB0aW9uIjoiPHA+QSBtYXJibGUgZmFjdG9yeSBoYXMgZG9uYXRlZCBhIGxhcmdlIGJveCBvZiBtYXJibGVzIHRvIGEga2luZGVyZ2FydGVuLiBFYWNoIG1hcmJsZSBoYXMgb25lIG91dCBvZiBNIGRpZmZlcmVudCBjb2xvdXJzLiBUaGUgZ292ZXJuZXNzIG5lZWRzIHRvIGRpdmlkZSBhbGwgdGhlIG1hcmJsZXMgYmV0d2VlbiB0aGUgTiBjaGlsZHJlbiBpbiBoZXIgZ3JvdXAuIEl0IGlzIGFjY2VwdGFibGUgaWYgc29tZSBjaGlsZHJlbiBkb24mIzM5O3QgZ2V0IGFueSBtYXJibGVzLiBIb3dldmVyLCBubyBjaGlsZCB3YW50cyBtYXJibGVzIG9mIGRpZmZlcmVudCBjb2xvdXJzICZuZGFzaDsgaW4gb3RoZXIgd29yZHMsIGFsbCBtYXJibGVzIHRoYXQgYSBjaGlsZCBnZXRzIG5lZWQgdG8gYmUgdGhlIHNhbWUgY29sb3VyLjxcL3A+XHJcblxyXG48cD5UaGUgZ292ZXJuZXNzIGFsc28ga25vd3MgdGhhdCBjaGlsZHJlbiB3aWxsIGJlIGplYWxvdXMgaWYgYSBjaGlsZCBnZXRzIHRvbyBtYW55IG1hcmJsZXMuIEFzIGFuIGFwcHJveGltYXRpb24sIHdlIHdpbGwgZGVmaW5lIHRoZSBlbnZ5IGxldmVsIGluIHRoZSBncm91cCBhcyB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgbWFyYmxlcyBnaXZlbiB0byBvbmUgY2hpbGQuIEhlbHAgdGhlIGdvdmVybmVzcyBkaXZpZGUgdGhlIG1hcmJsZXMgaW4gb3JkZXIgdG8gbWluaW1pemUgdGhlIGVudnkgbGV2ZWwuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiB0aGUgYm94IGNvbnRhaW5zIDQgcmVkIG1hcmJsZXMgKFJSUlIpIGFuZCA3IGJsdWUgbWFyYmxlcyAoQkJCQkJCQikgd2hpY2ggd2UgaGF2ZSB0byBkaXZpZGUgYmV0d2VlbiA1IGNoaWxkcmVuLCB3ZSBjYW4gYWNoaWV2ZSBhbiBlbnZ5IGxldmVsIG9mIDMgYnkgZGl2aWRpbmcgdGhlIG1hcmJsZXMgaW4gdGhlIGZvbGxvd2luZyB3YXk6IFJSLCBSUiwgQkIsIEJCLCBCQkIuIFRoaXMgaXMgdGhlIGxvd2VzdCBhY2hpZXZhYmxlIGVudnkgbGV2ZWwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMsIE4gKDEgJmxlOyBOICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgdGhlIG51bWJlciBvZiBjaGlsZHJlbiwgYW5kIE0gKDEgJmxlOyBNICZsZTsgMzAwIDAwMCwgTSAmbGU7IE4pLCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBjb2xvdXJzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgZnJvbSB0aGUgaW50ZXJ2YWwgWzEsIDEwPHN1cD45PFwvc3VwPl0sIHdpdGggdGhlIGludGVnZXIgaW4gbGluZSBLIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgbWFyYmxlcyB3aXRoIGNvbG91ciBLLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbWluaW11bSBwb3NzaWJsZSBlbnZ5IGxldmVsLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=