Trộn xâu

Cho $2$ xâu ký tự $X=x_1,x_2,\dots ,x_m$ và $Y=y_1,y_2,\dots ,y_n$. Cần xây dựng xâu $T=t_1,t_2,t_3,\dots ,t_{n+m}$ gồm tất cả các ký tự trong xâu $X$ và tất cả các ký tự trong xâu $Y$, sao cho các ký tự trong $X$ xuất hiện trong $T$ theo thứ tự xuất hiện trong $X$ và các ký tự trong $Y$ xuất hiện trong $T$ theo đúng thứ tự xuất hiện trong $Y$, đồng thời với tổng chi phí trộn là nhỏ nhất. Tổng chi phí trộn hai xâu $X$ và $Y$ để thu được xâu $T$ được tính bởi công thức:

$$c(T)=\sum _{k=1}^{n+m-1}c(t_k,t_{k+1})$$

trong đó, các chi phí $c(t_k,t_{k+1})$ được tính như sau:

• Nếu hai ký tự liên tiếp $t_k$, $t_{k+1}$ được lấy từ cùng một xâu $X$ hoặc $Y$ thì $c(t_k,t_{k+1})=0$.
• Nếu hai ký tự liên tiếp $t_k$, $t_{k+1}$ là $x_i$, $y_j$ thì chi phí phải trả là $c(x_i,y_j)$. Nếu hai ký tự liên tiếp $t_k$, $t_{k+1}$ là $y_j$, $x_i$ thì chi phí phải trả là $c(y_j,x_i)=c(x_i,y_j)$.

Dữ liệu vào

• Dòng đầu tiên chứa $Q$ là số lượng bộ dữ liệu. Tiếp đến là $Q$ nhóm dòng, mỗi nhóm cho thông tin về $1$ bộ dữ liệu theo khuôn dạng sau:
• Dòng thứ nhất chứa $2$ số nguyên dương $m$, $n$ ($m,n\le 1000$).
• Dòng thứ $i$ trong $m$ dòng tiếp theo chứa $n$ số nguyên dương, mỗi số không vượt quá ${10}^9$: $c(x_i,y_1),c(x_i,y_2),\dots ,c(x_i,y_n)$, $i=1,2,\dots ,m$.

Dữ liệu ra

Gồm $Q$ dòng, mỗi dòng chứa một số nguyên là tổng chi phí theo cách xây dựng xâu $T$ tìm được tương ứng với bộ dữ liệu vào.

Ràng buộc

• $1\le Q\le 10$.
• $1\le m,n\le 1000$; trong một test, tổng các tích $m·n$ không vượt quá ${10}^6$.
• $1\le c(x_i,y_j)\le {10}^9$.

Subtasks

• Subtask 1 ($60\%$ số test): $m,n\le 10$.
• Subtask 2 ($40\%$ số test): không có ràng buộc gì thêm.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ