Các bạn có biết trò chơi gây nghiện Flappy Bird của Nguyễn Hà Đông không? Trong bài ngày hôm nay của chúng ta có một con chim ngu ngốc bay vào một cái hang với các chướng ngại vật là các măng đá (mọc lên từ đáy hang) và nhũ đã (nhô xuống từ trần hàng).
Con chim này không biết bay lên xuống để tránh các chướng ngại vật như con chim của Nguyễn Hà Đông mà thay vào đó, nó sẽ chọn một mức chiều cao bắt đầu rồi bay từ đầu đến cuối hang, phá hết tất cả các chướng ngại vật trên đường bay của nó.
Nếu chọn bay ở những độ cao khác nhau thì số chướng ngại vật nó phải phá là khác nhau. Theo ví dụ trên, nếu chọn mức , con chim sẽ phá tất cả là chướng ngại vật. Đây không phải là lựa chọn tốt nhất vì con chim sẽ ít mệt hơn nếu chọn mức hoặc mức , lúc này nó chỉ cần phá chướng ngại vật.
Bạn được cho biết số là số chướng ngại vật, là chiều cao của hang, thông tin về các chướng ngại vật. Hãy xác định số chướng ngại vật tối thiểu mà con chim cần phá để đi qua hang.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương và được ghi cách nhau một dấu cách.
Dòng thứ hai chứa số nguyên khác , hai số liên tiếp được ghi cách nhau một dấu cách. Nếu thì đó là măng đá mọc lên từ đáy hang với độ dài , nếu thì đó là nhũ đá nhô xuống từ trần hang với độ dài .
Dữ liệu ra:
Ghi trên một dòng số nguyên là số chướng ngại vật tối thiểu cần xuyên phá.
