Một hành giả (nhà tu hành) muốn đến được Tây Trúc cần lần lượt thỉnh hết N ngôi chùa (các ngôi chùa được đánh số từ 1 đến N theo trình tự thỉnh) đồng thời phải trút bỏ hết số hồ lô mang trên người sau khi thỉnh hết N ngôi chùa đó và tích lũy được càng nhiều càng tốt số hạt xá lợi khi kết thúc hành trình. Tại mỗi ngôi chùa đều đặt một hồ lô có chứa một số nào đó các hạt xá lợi: hồ lô ở ngôi chùa i có chứa Xi hạt.

Xuất phát từ ngôi chùa 1 (trước khi xuất phát, hành giả không có hồ lô nào mang trên người), mỗi khi đặt chân đến một ngôi chùa i hành giả có thể có một trong hai lựa chọn:

• Lấy quả hồ lô ở đó và được thu giữ toàn bộ xá lợi có trong hồ lô. Trường hợp này khiến hành giả phải mang theo trên người hồ lô này để tiếp tục hành trình.
• Bỏ qua, không lấy quả hồ lô đó. Trường hợp này khiến hành giả không lấy được số xá lợi có trong hồ lô.

Việc lấy thêm hoặc trút bỏ bớt hồ lô phải tuân theo quy tắc nghiêm ngặt sau đây.

Khi đang thỉnh tại chùa i (1 ≤ i ≤ N) và số hồ lô đang mang trên người là K (K ≥ 0) thì:

1. Trong mọi tình huống, hành giả được quyền không lấy hồ lô tại đây nếu muốn.
2. Hành giả chỉ được lấy thêm hồ lô tại đây khi một trong hai trường hợp sau xảy ra:
   • Trường hợp 1:  K = 0
   • Trường hợp 2:  0 < K < M và trước đó, tại chùa i -1 hành giả có lấy hồ lô.
3. Hành giả chỉ được bỏ bớt đúng một hồ lô mang trên người khi K > 0 đồng thời tại chùa này hành giả đã không lấy hồ lô.

Như vậy, nếu tại chùa i hành giả không lấy hồ lô và số hồ lô đang mang trên người là K thì hành giả được trút bỏ bớt 1 hồ lô tại đây nhưng nếu K > 1 thì hành giả không được lấy hồ lô tại K-1 chùa tiếp theo để trút bỏ hết K-1 hồ lô đó rồi mới có thể tiếp tục lấy thêm hồ lô (nếu còn và nếu muốn).

Yêu cầu: Xác định số S, là số nhiều nhất hạt xá lợi mà hành giả có thể thu được sau khi đến được Tây Trúc.

Dữ liệu: Đọc từ file văn bản TAYTRUC.INP, có cấu trúc:

• Dòng đầu ghi lần lượt 2 số nguyên N và M (2 ≤ N ≤ 10000; 1 ≤ M ≤ 500);
• N dòng tiếp theo, mỗi dòng ghi một số nguyên dương: dòng i+1 ghi số Xi, (Xi  ≤ 1000).

Kết quả:  Ghi ra file văn bản TAYTRUC.OUT duy nhất số nguyên S tìm được.

Ví dụ:

Input
9 4 
1 
9 
8 
3 
4 
9 
8 
9 
7 

Output
35 

Giải thích: Hành giả sẽ lấy hồ lô tại các chùa 2, 3, 6, 8.