In preparation for a sports tournament, you have n training exercises available. Completing the i$-$th exercise improves your skills by arr$[$i$]$ points. You can only perform one exercise per day, and once you complete an exercise, you must wait k days before repeating it$.$ For example, if k$=2$ and you perform exercise $1$ on day $1,$ you cannot repeat it on days $2$ and $3,$ but can do it again on day $4.$

Given two targets: achieve at least c skill points within d days. Determine the maximum k that allows you to meet this goal. If no such k exists or k is arbitrarily large, output $-1.$

Examples:

Input:

$254$

$12$

Output:

$2$

Explanation:

In the given example, one way to gain $5$ skill point over $4$ days with K$=2$ is as follows:

Day $1$: do exercise $2,$ and gain $2$ skill points.

Day $2$: do exercise $1,$ and gain $1$ skill points.

Day $3$: do nothing.

Day $4$: do exercise $2,$ and gain $2$ skill points.

In total, we gained $2+1+2=5$ skill points.

Input$/$Output

$[$execution time limit$]0\mathrm{.}5$ seconds $($cpp$)$

$[$memory limit$]1$ GB

$[$input$]$ integer n

Number of exercises

Guaranteed constraints:

$2<=$ n $<=2*105$

$[$input$]$ integer$64$ c

Amount of skill points you have to gain atleast within d days

Guaranteed constraints:

$1<=$ c $<=1016$

$[$input$]$ integer d

Number of days

Guaranteed constraints:

$1<=$ d $<=2*105$

$[$input$]$ array.integer arr

Represent skill points you gained on completing ith exercise

Guaranteed constraints:

$1<=$ arr$[$i$]<=109$

$[$output$]$ integer$64$

The maximum k that allows you to gain atleast c skill point within d days, if not possible or k is arbitrary large then return $-1$