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 a₁ people speak the first dialect, at least a₂ people speak the second dialect, …, at least a_k people speak the k-th dialect. How many people speak all k dialects if the population of China is n people?

The first line contains integers n and k (2 ≤ k ≤ 20; 1 ≤ n ≤ 10⁹). The second line contains space-separated integers a₁, …, a_k (1 ≤ a_k ≤ n).

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