Đường đi dây sạc

Time limit: 1.0s , Memory limit: 64M , Points: 1

Nhân dịp được nghỉ lễ dài ngày, anh $S$ ~S~ quyết định nằm lười xem ``Flash''. Nhưng không may, một antifan đã sử dụng tà thuật để biến dây sạc của anh ấy thành $M$ ~M~ mảnh.

Các mảnh dây sạc được đánh số từ $1$ ~1~ đến $M$ ~M~, tương ứng với thứ tự đúng khi nối lại thành một sợi dây hoàn chỉnh.

Sau khi bị phá hỏng, các mảnh dây sạc được chia vào $N$ ~N~ hàng. Ban đầu, hàng thứ $i$ ~i~ chứa $A_i$ ~A_i~ mảnh. Trong một lần di chuyển, anh S được phép chọn một mảnh bất kỳ từ một hàng và chuyển nó sang một hàng khác.

Anh S muốn sắp xếp lại các mảnh sao cho khi nối các hàng theo thứ tự từ hàng $1$ ~1~ đến hàng $N$ ~N~, dây sạc được nối đúng theo thứ tự tăng dần $1, 2, 3, \ldots, M$ ~1, 2, 3, \ldots, M~.

Thứ tự các mảnh trong cùng một hàng không quan trọng. Ta xem như các mảnh trong mỗi hàng có thể được sắp xếp lại tự do mà không tốn thêm thao tác.

Nói cách khác, sau khi sắp xếp xong, nếu gọi $row_x$ ~row_x~ là chỉ số hàng chứa mảnh dây số $x$ ~x~, thì dãy $row_1, row_2, \ldots, row_M$ ~row_1, row_2, \ldots, row_M~ phải là một dãy không giảm.

Không bắt buộc tất cả các hàng đều phải có mảnh dây. Một số hàng có thể rỗng, thậm chí chỉ một hàng chứa toàn bộ các mảnh dây và các hàng còn lại không chứa mảnh nào.

Hãy tính số lần di chuyển ít nhất để anh S nối lại dây sạc và không bỏ lỡ trận đấu nào.

Input

Dòng đầu tiên chứa số nguyên $N$ ~N~ là số hàng chứa các mảnh dây sạc.

Dòng thứ hai chứa $N$ ~N~ số nguyên $A_1, A_2, \ldots, A_N$ ~A_1, A_2, \ldots, A_N~, trong đó $A_i$ ~A_i~ là số mảnh dây sạc ban đầu ở hàng thứ $i$ ~i~.

Trong $N$ ~N~ dòng tiếp theo, dòng thứ $i$ ~i~ chứa $A_i$ ~A_i~ số nguyên, là các mảnh dây sạc ban đầu nằm ở hàng thứ $i$ ~i~.

Đặt $M = A_1 + A_2 + \ldots + A_N$ ~M = A_1 + A_2 + \ldots + A_N~.

Dữ liệu đảm bảo:

$1 \le N \le 200$ ~1 \le N \le 200~;
$N \le M \le 10^5$ ~N \le M \le 10^5~;
mỗi mảnh dây sạc là một số nguyên phân biệt từ $1$ ~1~ đến $M$ ~M~.

Output

In ra một số nguyên duy nhất là số lần di chuyển ít nhất cần thực hiện để nối lại dây sạc.

Samples

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Scoring

Subtask 1: $30$ ~30~ điểm. $M \le 1000$ ~M \le 1000~ và $N = 3$ ~N = 3~.
Subtask 2: $40$ ~40~ điểm. $M \le 10^5$ ~M \le 10^5~ và $N \le 8$ ~N \le 8~.
Subtask 3: $30$ ~30~ điểm. Không có ràng buộc bổ sung.

Notes

Ở ví dụ thứ nhất, hàng thứ nhất chứa các mảnh $2, 1$ ~2, 1~, hàng thứ hai chứa các mảnh $4, 3$ ~4, 3~, và hàng thứ ba chứa các mảnh $6, 5$ ~6, 5~.

Vì thứ tự các mảnh trong cùng một hàng không quan trọng, ta có thể sắp xếp lại các mảnh trong từng hàng thành $1, 2$ ~1, 2~ ở hàng thứ nhất, $3, 4$ ~3, 4~ ở hàng thứ hai, và $5, 6$ ~5, 6~ ở hàng thứ ba.

Khi nối hàng $1$ ~1~, rồi đến hàng $2$ ~2~, rồi đến hàng $3$ ~3~, ta thu được dãy $1, 2, 3, 4, 5, 6$ ~1, 2, 3, 4, 5, 6~. Do đó dây sạc đã được nối hoàn chỉnh và không cần thực hiện thao tác di chuyển nào.

Ở ví dụ thứ hai, hàng thứ nhất chứa các mảnh $5, 6$ ~5, 6~, hàng thứ hai chứa mảnh $4$ ~4~, và hàng thứ ba chứa các mảnh $1, 2, 3$ ~1, 2, 3~.

Ta có thể chuyển các mảnh $5, 6$ ~5, 6~ từ hàng thứ nhất sang hàng thứ ba, và chuyển mảnh $4$ ~4~ từ hàng thứ hai sang hàng thứ ba.

Khi đó bảng trở thành:

Hàng $1$ ~1~: rỗng.

Hàng $2$ ~2~: rỗng.

Hàng $3$ ~3~: $1, 2, 3, 4, 5, 6$ ~1, 2, 3, 4, 5, 6~.

Khi nối hàng $1$ ~1~, hàng $2$ ~2~, rồi đến hàng $3$ ~3~, ta thu được dãy $1, 2, 3, 4, 5, 6$ ~1, 2, 3, 4, 5, 6~. Do đó dây sạc đã được nối hoàn chỉnh.

Cần di chuyển các mảnh $4, 5, 6$ ~4, 5, 6~, nên số lần di chuyển là $3$ ~3~.