Book and Stamps

Problem Description

In the Royal Library, archivists write magic books. To complete the next book, the $i$-th letter must be used at least $C[i]$ times. Remember that the country uses an alphabet of $n$ letters.

A stamp is a piece of sticky paper with $m$ letters written on it (letters may repeat). The appearance of the stamp, which letters are written on it, etc., is agreed upon in advance and cannot be changed. After agreeing on the appearance of the stamp, based on this agreement an unlimited number of stamps will be created.

The book will be printed using these stamps. Only one stamp may be affixed to one page of the book.

If you can choose $m$ letters for the stamp design, find the minimum number of pages needed to write the book.

If it is impossible to write the book, i.e. even an unlimited number of stamps will not be enough, then output $-1$.

Input Format

The first line gives $n$ --- the number of letters in the alphabet and $m$ --- the number of letters in the stamp.

The second line gives $n$ integers $C[i]$ --- the minimum required number of the $i$-th letter to write the book.

Constraints:

• $1 \leq n \leq 200\,000$
• $0 \leq m \leq 10^{18}$
• $0 \leq C[i] \leq 10^9$

Output Format

Output the minimum number of pages to write the book, given that you are designing the stamp. If this is impossible, output $-1$.

Scoring

Notes

In the first test, no matter how many stamps there are, it is impossible to make $3$ different letters from a stamp that holds $2$ symbols.