Có ~n~ khay bánh xếp theo thứ tự từ ~1~ đến ~n~ trên một bàn dài. Khay thứ ~i~ ban đầu có ~a_i~ chiếc bánh.

Người chơi có đúng ~k~ lượt đi (theo thứ tự thời gian). Ở mỗi lượt, người chơi chọn một đoạn liên tiếp ~[L, R]~ và ăn đúng 1 chiếc ở mỗi khay từ ~L~ đến ~R~.

Người chơi không được chọn đoạn ~[L,R]~ nếu trong đoạn đó tồn tại khay đã rỗng (vì không còn bánh để ăn), tức là tại thời điểm chọn, mọi khay trong ~[L,R]~ phải còn ít nhất 1 chiếc.

Sau ~k~ lượt, số khay rỗng là số khay có số bánh còn lại bằng ~0~. Mục tiêu là làm rỗng nhiều khay nhất có thể.

Yêu cầu

Hãy xác định số khay rỗng lớn nhất có thể đạt được sau đúng ~k~ lượt chơi.

Dữ liệu

• Dòng 1: hai số nguyên ~n~ và ~k~.
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~.

Kết quả

In ra một số nguyên — số khay rỗng lớn nhất có thể làm rỗng.

Ví dụ

Ví dụ 1

Input

6 5
1 5 3 2 1 4

Output

5

Giải thích

Ví dụ 1

Có một chiến lược giúp làm rỗng được ~5~ khay sau ~5~ lượt, và không thể làm rỗng cả ~6~ khay trong giới hạn ~k=5~ lượt.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 2000~
• ~1 \le k \le 10^9~
• ~1 \le a_i \le 10^9~ với mọi ~i~