DA-S95-CA1

Time Limit: 1 Second    Memory Limit: 65536 KB

پویا یک دستگاه بستنی سازی دارد که از k لوله ی موازی از آن بستنی خارج می شود. او باید n بستنی لیوانی برای یکی از مشتریانش آماده کند. در ابتدا در لیوان های مختلف مقادیر متفاوتی از خوارکی های متنوع ریخته و سپس با استفاده از دستگاه بستنی سازی قصد دارد روی آن ها بستنی بریزد. مشکل این جاست که ارتفاع خوراکی های داخل لیوان های مختلف متفاوت است و مشتری از ابتدا تعیین کرده بود که به نسبت اندازه ی کمترین ارتفاع پر شده در بین بستنی های لیوانی به او پول پرداخت خواهدکرد. هم چنین پویا تنها قادر است m بار از دستگاه خود استفاده کند که هر بار از k لوله ی آن بستنی خارج شده و ارتفاع لیوان های زیر آن یک واحد افزایش می یابد. هدف پویا این است که در نهایت کمترین ارتفاع بستنی در لیوان ها بیشینه شود. الگوریتمی ارائه دهید که با گرفتن اعداد n, m, k و لیستی از ai ها که هر کدام نشان دهنده ی ارتفاع محتویات داخل لیوان i - ام قبل از ریختن بستی داخل آن است، بیشترین مقداری که کمترین ارتفاع بستنی در لیوان ها می تواند داشته باشد را بدست آورد.

Input

در اولین خط شامل اعداد صحیح ، و است که با فاصله از هم جدا شده اند. سپس در خط دوم، اعداد صحیح با فاصله از هم آمده اند.

Output

یک عدد صحیح که مقدار بیشترین ارتفاع برای کوتاه ترین بستنی است.

Sample Input

7 2 4
2 2 2 2 1 1 1

Sample Output

2

Submit