You are given N assignments by your professor.

He also gives you a list of integers TIME. ith assignment takes TIME[i] hours to complete it. ($1 \leq i \leq N$ )

You have to complete all the assignment in less than or equal to K days. However you won't work on an assignment for more than T hours in a day.

On each day you can select any assignment and work on it for T hours. If the choosen assignment requires less than T hours to complete, you still work on that assignment for T hours.

Find minimum T (no. of hours you will work each day), so that you complete all the assignments in less than or equal to K days)

INPUT

• First line contains N (no. of assignments)
• Second line contains N space seprated integers, ith integer denote the time required to complete the ith assignment ( $1 \leq i \leq N$)
• Last input contains K, maximum number of days you can take to complete all assignment

OUTPUT

• Print a single integer, T  (minimum no. of hours you will work each day to complete all the assignment in less than or equal to K days).

CONSTRAINTS

• $1 \leq N \leq 10^6$
• $1 \leq TIME[i] \leq 10^{12}$
• $N \leq K \leq 10^{18}$

Warning : Large I/O. Use fast I/O methods.

NOTE : A day is of 10^12 hours.