ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural FU Personal Contest 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Chinese Dialects

Time limit: 1.0 second
Memory limit: 64 MB
Vova moved from Guangzhou to Shenzhen. He immediately found out that the local people don't understand his Cantonese phrases as well. Vova tried chatting with them in Mandarin, but to no success.
Then Vova decided to learn more about Chinese dialects. It turned out that people in China speak k different dialects, at that at least a1 people speak the first dialect, at least a2 people speak the second dialect, …, at least ak people speak the k-th dialect. How many people speak all k dialects if the population of China is n people?

Input

The first line contains integers n and k (2 ≤ k ≤ 20; 1 ≤ n ≤ 109). The second line contains space-separated integers a1, …, ak (1 ≤ akn).

Output

Print the minimum number of people in China that speak all k dialects of the Chinese language.

Samples

inputoutput
1000000000 2
800000000 800000000
600000000
1000000000 2
500000000 500000000
0
Problem Author: Alexander Ipatov
Problem Source: Open Ural FU Personal Contest 2013
To submit the solution for this problem go to the Problem set: 1964. Chinese Dialects