Mùa đông đã đến ở trang trại, và điều đó có nghĩa là tuyết! Có \(N\) ô lát trên con đường từ nhà đến chuồng bò, được đánh số thuận tiện từ \(1 \dots N\), và ô \(i\) bị phủ bởi lớp tuyết sâu \(f_i\) feet.

Bác nông dân John bắt đầu tại ô \(1\) và phải đến ô \(N\) để đánh thức đàn bò. Ô \(1\) được mái nhà che chắn còn ô \(N\) được mái chuồng che chắn, nên cả hai ô này đều không có tuyết. Nhưng để bước lên các ô còn lại, bác nông dân John cần đi ủng!

Trong ba lô dùng khi thời tiết xấu, bác nông dân John có \(B\) đôi ủng, được đánh số từ \(1 \dots B\). Một số đôi chịu được điều kiện khắc nghiệt hơn những đôi khác, còn một số đôi linh hoạt hơn những đôi khác. Cụ thể, đôi \(i\) cho phép bác nông dân John bước vào lớp tuyết sâu tối đa \(s_i\) feet và tiến về phía trước tối đa \(d_i\) ô trong mỗi bước.

Không may, những đôi ủng được xếp theo cách khiến bác nông dân John tại mỗi thời điểm chỉ có thể lấy đôi nằm trên cùng. Vì vậy, vào bất kỳ lúc nào, ông có thể đi đôi ủng trên cùng (vứt bỏ đôi cũ) hoặc vứt bỏ đôi ủng trên cùng (để có thể lấy một đôi mới).

Bác nông dân John chỉ có thể đổi ủng khi đang đứng trên một ô. Nếu ô đó có lớp tuyết sâu \(f\) feet thì cả đôi ủng ông cởi ra VÀ đôi ủng ông đi vào đều phải chịu được lớp tuyết sâu ít nhất \(f\) feet. Những đôi ủng trung gian mà ông vứt đi mà không mang không cần thỏa mãn hạn chế này.

Hãy giúp bác nông dân John giảm thiểu lãng phí bằng cách xác định số đôi ủng ít nhất ông cần vứt bỏ để đến được chuồng bò. Có thể giả sử rằng ban đầu bác nông dân John không đi đôi ủng nào.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\) cách nhau bởi dấu cách (\(2 \leq N,B \leq 250\)).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách. Số nguyên thứ \(i\) là \(f_i\), độ sâu của tuyết trên ô \(i\) (\(0 \leq f_i \leq 10^9\)). Bảo đảm rằng \(f_1 = f_N = 0\).

\(B\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách. Số nguyên đầu tiên trên dòng \(i+2\) là \(s_i\), độ sâu tuyết lớn nhất mà đôi ủng \(i\) có thể bước vào. Số nguyên thứ hai trên dòng \(i+2\) là \(d_i\), độ dài bước chân lớn nhất của đôi ủng \(i\). Bảo đảm rằng \(0 \leq s_i \leq 10^9\) và \(1 \leq d_i \leq N-1\).

Các đôi ủng được mô tả theo thứ tự từ trên xuống dưới, nên đôi \(1\) là đôi nằm trên cùng trong ba lô của bác nông dân John, và cứ tiếp tục như vậy.

Dữ liệu ra

In ra một số nguyên duy nhất là số đôi ủng ít nhất mà bác nông dân John cần vứt bỏ. Bảo đảm rằng bác nông dân John có thể đến được chuồng bò.

Ví dụ

10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1

2

Nguồn

USACO 2018 February Contest, Silver — Snow Boots

Tác giả bài toán: Brian Dean và Dhruv Rohatgi.