Input
2 1
1 1
Output
4
Input
3 2
1 0 2
Output
5
Input
4 100
3 4 5 4
Output
5