Sắp xếp ghế rạp chiếu phim (bản khó)

Một rạp chiếu phim có $n$ hàng ghế, mỗi hàng có $m$ ghế. Các ghế được đánh số từ $1$ đến $nm$ theo thứ tự: hàng $k$ chứa các ghế có chỉ số từ $m(k-1)+1$ đến $mk$ (đánh từ trái sang phải).

Có $nm$ người (đánh số từ $1$ đến $nm$) cùng vào xem phim. Người thứ $i$ có độ thị lực $a_i$. Mỗi người được xếp đúng một ghế; gọi $s_i$ là chỉ số ghế xếp cho người $i$. Phải xếp sao cho người có thị lực kém hơn được ghế có chỉ số nhỏ hơn, tức là với mọi cặp $i,j$ mà $a_i<a_j$ thì $s_i<s_j$ (nếu $a_i=a_j$ thì $s_i,s_j$ tùy ý).

Sau khi xếp chỗ xong, lần lượt theo thứ tự $1,2,\dots ,nm$, từng người sẽ đi vào hàng chứa ghế của mình và đi từ ghế đầu hàng (trái nhất) tới ghế của mình. Trên đường đi, một số ghế có thể đã có người ngồi. Độ bất tiện của một người bằng số ghế đã có người ngồi mà người đó phải đi qua trước khi tới ghế của mình.

Hãy xếp chỗ để tổng độ bất tiện của tất cả $nm$ người là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ($1\le t\le 100$) — số test.

Với mỗi test:

• Dòng thứ nhất chứa hai số nguyên $n,m$ ($1\le n,m\le 300$).
• Dòng thứ hai chứa $n·m$ số nguyên $a_1,a_2,\dots ,a_{nm}$ ($1\le a_i\le {10}^9$).

Tổng $n·m$ trên tất cả các test không vượt quá ${10}^5$.

Dữ liệu ra

Với mỗi test, in ra một số nguyên là tổng độ bất tiện nhỏ nhất có thể đạt được.

Ràng buộc

• $1\le t\le 100$
• $1\le n,m\le 300$
• $1\le a_i\le {10}^9$
• Tổng $n·m\le {10}^5$

Ví dụ