Đã đến mùa đông ở trang trại, nghĩa là có tuyết! Có $N$ ô lát trên đường từ nhà đến chuồng, được đánh số $1 \dots N$, và ô $i$ bị phủ tuyết sâu $f_i$ feet.

Farmer John bắt đầu ở ô $1$ và phải đến ô $N$ để đánh thức bò. Ô $1$ được mái nhà che, ô $N$ được mái chuồng che nên cả hai không có tuyết. Nhưng để bước lên các ô khác, ông cần đi ủng!

Trong ba lô dành cho thời tiết xấu, ông có $B$ đôi ủng, đánh số $1 \dots B$. Có đôi bền hơn, có đôi linh hoạt hơn. Đôi $i$ cho phép bước vào tuyết sâu tối đa $s_i$ feet và tiến về trước tối đa $d_i$ ô mỗi bước.

Không may, cách xếp khiến ông chỉ có thể lấy đôi trên cùng tại mọi thời điểm. Ông có thể đi đôi trên cùng và bỏ đôi cũ, hoặc bỏ đôi trên cùng để lấy được đôi tiếp theo.

Ông chỉ được đổi ủng khi đứng trên một ô. Nếu ô đó có tuyết sâu $f$ feet, cả đôi tháo ra VÀ đôi đi vào đều phải chịu được ít nhất $f$ feet tuyết. Các đôi ở giữa bị bỏ mà không đi không cần thỏa mãn giới hạn này.

Để giảm lãng phí, hãy tìm số đôi ủng ít nhất cần bỏ để đến chuồng. Có thể giả sử ban đầu ông không đi ủng.

Dữ liệu vào

Dòng đầu 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ố thứ $i$ là $f_i$, độ sâu tuyết ở ô $i$ ($0 \leq f_i \leq 10^9$). Đảm bảo $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ố đầu trên dòng $i+2$ là $s_i$, độ sâu tuyết tối đa đôi $i$ có thể bước vào. Số thứ hai trên dòng $i+2$ là $d_i$, độ dài bước tối đa của đôi $i$. Đảm bảo $0 \leq s_i \leq 10^9$ và $1 \leq d_i \leq N-1$.

Ủng được mô tả theo thứ tự từ trên xuống dưới, nên đôi $1$ ở trên cùng ba lô, và cứ như vậy.

Dữ liệu ra

In một số nguyên: số đôi ủng ít nhất cần bỏ. Đảm bảo ông có thể đến chuồng.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2

Tác giả: Brian Dean và Dhruv Rohatgi