Sắp bài số lượng lớn

Trên tay Maverick có \(C \cdot N\) lá bài xếp thành một hàng (theo thứ tự từ trái sang phải như input). Lá bài được xác định bởi màu \(X\) (\(1 \le X \le C\)) và giá trị \(Y\) (\(1 \le Y \le N\)), mỗi cặp \((X, Y)\) xuất hiện đúng một lần.

Mục tiêu là đưa hàng bài về trạng thái: các lá cùng màu liền nhau thành từng khối (khối màu nào đứng trước cũng được) và trong mỗi khối giá trị tăng dần từ trái sang phải.

Mỗi lần Maverick được rút một lá bài bất kỳ ra và nhét vào một chỗ tuỳ ý trong hàng. Tìm số lần rút-nhét ít nhất để đạt mục tiêu.

Input

• Dòng đầu tiên gồm hai số nguyên \(C\) và \(N\).
• Tiếp theo là \(C \cdot N\) dòng, mỗi dòng hai số nguyên \(X\) và \(Y\) mô tả một lá bài, theo thứ tự trên tay từ trái sang phải. Các lá bài đôi một khác nhau.

Output

In ra số lần rút-nhét tối thiểu.

Constraints

• \(1 \le C \le 4\)
• \(1 \le N \le 25000\)
• \(1 \le X \le C\), \(1 \le Y \le N\)

Sample Input

2 3
1 2
2 3
1 1
2 1
1 3
2 2

Sample Output

3

Explanation

Có thể giữ nguyên ba lá \((1,2)\), \((1,3)\), \((2,2)\) (theo đúng thứ tự xuất hiện này chúng đã nằm đúng vị trí tương đối nếu khối màu \(1\) đứng trước khối màu \(2\)), và di chuyển ba lá còn lại vào đúng chỗ. Không thể giữ được nhiều hơn ba lá nên đáp án là \(3\).