题目描述

Churro, a chubby and energetic guinea pig, has just started a new job at a fancy restaurant called Jaime's Palace. Since she is the newest employee, she is only responsible for washing and arranging the plates. Churro discovered that the most efficient way to keep the plates organized and easily accessible for the chef is by storing them in a single stack.

There are $P$ plates in Jaime's Palace, and $K_i$ of them are used on the $i$-th day. Churro designed a rigid and highly logical system for managing the plates. On the $i$-th day she takes the top $K_i$ plates from the stack and the chef uses each of them just once during the day. At the end of the day, Churro washes the $K_i$ used plates and places them back on top of the stack in an arbitrary order.

Churro's system is a real success. However, she is curious about the following questions. After repeating the above procedure for $D$ days, can she be sure that there is a plate that was used at least $t$ times? What is the maximum value of $t$ that she can guarantee? Please help Churro to determine that value.

输入格式

The first line contains two integers $P$ ($2 \le P \le 2000$) and $D$ ($1 \le D \le 2000$), indicating respectively the number of plates and the number of days.

The second line contains $D$ integers $K_1, K_2, \ldots, K_D$ ($1 \le K_i \le P$ for $i = 1, 2, \ldots, D$), where $K_i$ is the number of plates used on the $i$-th day.

输出格式

Output a single line with an integer indicating the maximum value of $t$ such that after $D$ days and for any reordering of the plates put back into the stack at the end of each day, there is a plate that was used at least $t$ times.

10 3
1 1 2

3

10 4
5 3 5 2

3

提示

Explanation of Sample 1:

On each of the first two days, Churro takes the top plate from the stack and places it back on top, so that plate is used twice. On the third day she takes the top two plates, so one of those plates is used three times, independently of the order in which the plates are placed back on top of the stack at the end of the third day.