Nhân dịp trung thu, các bạn tình nguyên viên Bedao được thưởng một thùng toàn là kẹo. Vì em bé FireGhost và TrungNotChung nhỏ nhất nên được ưu tiên lấy kẹo trước. Thùng kẹo có ~k~ viên kẹo nhưng không em nào nhường em nào. Hai em đã nghĩ ra trò chơi như sau:

Cho một dãy có ~n~ phần tử, phần tử thứ ~i~ có giá trị ~1 \leq a_i \leq k~. Mỗi lượt một trong hai em sẽ chọn ra một số nguyên ~a_i~ trong dãy, có giá trị không vượt quá số lượng kẹo còn lại, và bốc ra khỏi thùng kẹo ~a_i~ viên. Các giá trị ~a_i~ có thể được dùng nhiều lần. Trò chơi dừng lại khi không thể bốc được thêm.

Hai em chơi luân phiên theo lượt, FireGhost chơi trước, hãy tìm lượng kẹo nhiều nhất FireGhost có thể bốc được, nếu như cả hai em cùng chơi tối ưu nhé.

Input

• Dòng đầu chứa hai số nguyên dương ~k, n~ ~(1 \leq n \leq 100, 1 \leq k \leq 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1 \leq a_i \leq k)~ mô tả dãy ~a~.

• Dữ liệu đảm bảo ~a_1 = 1~.

Output

• Gồm một số nguyên duy nhất là lượng kẹo nhiều nhất FireGhost có thể bốc được, nếu như hai em cùng chơi tối ưu.

Sample Input 1

10 3
1 3 4

Sample Output 1

6

Notes

Tại lượt đầu tiên, FireGhost bốc ra khỏi thùng kẹo ~3~ viên.

• Nếu TrungNotChung bốc ra ~4~ viên thì FireGhost bốc ra ~3~ viên, TrungNotChung kết thúc trò chơi với ~4~ viên kẹo.

• Nếu TrungNotChung bốc ra ~3~ viên thì FireGhost bốc ra ~4~ viên, TrungNotChung kết thúc trò chơi với ~3~ viên kẹo.

• Nếu TrungNotChung bốc ra ~1~ viên thì FireGhost bốc ra ~4~ viên. Khi đó, lượng kẹo còn lại là ~2~ viên nên TrungNotChung sẽ kết thúc trò chơi với nhiều nhất là ~3~ viên kẹo.

TrungNotChung chơi tối ưu nên sẽ bốc ra ~4~ viên kẹo và FireGhost bốc ra ~3~ viên kẹo còn lại.

Vậy FireGhost kết thúc trò chơi với ~6~ viên kẹo. Có thể chứng minh đây là lượng kẹo nhiều nhất FireGhost nhận được nếu cả hai bạn chơi tối ưu.