Trong một ngân hà xa, rất xa, kẻ bạo chúa một thời, Loli xuất hiện. Hắn là người hành tinh Alime, là người lưỡng tính. Là một người rất mê Light Novel, Loli rất muốn đến Trái Đất để mua vài bộ truyện mới ra. Hôm nay là ngày ra "Arya bàn bên", vì vậy Loli phải đáp tàu xuống Trái Đất để mua luôn, kẻo hết hàng Limited.

Bãi đỗ trên Trái Đất là một lưới ô vuông có ~N~ dòng và ~M~ cột, chứa nhiều tàu vũ trụ, mỗi tàu nằm gọn trên một ô vuông và có một giá trị riêng. Là một người độc ác, Loli muốn đỗ đè lên tàu càng đắt càng tốt.

Tàu của Loli có dạng hình chữ I: Nó có thể trải dài ra nhiều hàng một cách linh hoạt (ít nhất là ~3~ hàng, nhiều nhất là ~N~ hàng), tuy nhiên tàu chỉ chiếm ~3~ cột, với cột ~1~ và cột ~3~ rỗng đoạn từ hàng thứ ~2~ đến ~K-1~ (với ~K~ là số hàng mà tàu chiếm, ~3\le K \le N~).

Hỏi tổng giá trị tàu lớn nhất mà Loli phá được là bao nhiêu?

Input

• Dòng đầu gồm 1 số ~T\ (1 ≤ T ≤ 4)~ chỉ số test nhỏ trong test.
• Sau đó là các test. Dòng đầu tiên gồm 2 số ~N~ và ~M\ (1 ≤ N, M ≤ 400)~ chỉ kích cỡ bãi đỗ.
• Sau đó là ~N~ dòng, mỗi dòng gồm ~M~ số nguyên ~(0 ≤ |A_{ij}| ≤ 10^9)~ chỉ giá trị từng tàu.

Output

• Với mỗi test in trên một dòng một số duy nhất ghi đáp số.

Sample Input 1

1
4 3
1 1 1
1 0 1
1 2 1
1 1 1

Sample Output 1

8

Giải thích

Tàu đỗ như sau sẽ cho ra tổng giá trị là ~8~:

Các cách còn lại chỉ cho ra tổng giá trị là ~7~:

Ràng buộc

• 40% số điểm có ~N \le 40~.
• 60% số điểm còn lại không có ràng buộc gì thêm.

Loli hiện đang sử dụng một con laptop cổ lô sĩ. Mặc dù Loli không dùng gì quá nặng, tuy nhiên laptop của Loli luôn bị tràn RAM. Loli không biết làm gì để có thêm RAM. "Hay là mình lên mạng để tải thêm RAM nhỉ?" - Loli thắc mắc.

Sau khi lên mạng, Loli đã tìm ra một trang web khá "uy tín". Trang web đó rao bán ~n~ phần mềm giúp tăng RAM trong máy. Cụ thể như sau:

• Phần mềm tăng RAM thứ ~i~ cần ~a_i~ GB RAM để chạy (chúng chỉ chạy lần đầu tiên, sau khi chạy xong, số RAM đó sẽ được giải phóng để Loli làm việc khác).
• Sau khi chạy phần mềm thứ ~i~, máy của Loli sẽ được tăng thêm ~b_i~ GB RAM (tăng vĩnh viễn).

Mỗi phần mềm chỉ được mua một lần. Tại một thời điểm chỉ được dùng nhiều nhất một phần mềm. Laptop của Loli hiện tại chỉ có ~k~ GB RAM (Loli chưa mua phần mềm nào).

Vì nhà của Loli quá giàu nên Loli tất nhiên có thể mua hết đống phần mềm này. Dĩ nhiên, nếu phần mềm nào yêu cầu nhiều RAM hơn số lượng RAM máy Loli đang có thì phần mềm đó không thể chạy được.

Loli ngây thơ tin vào những quảng cáo sặc mùi scam đó. Bạn của Loli là Lilo sau khi nghe những lời Loli nói thì cười sặc hết cả nước mũi. Lilo thừa biết đó không phải là sự thật, tuy nhiên thay vì bảo Loli thì Lilo lại nhờ bạn làm một chương trình để tìm cách mua và sử dụng các phần mềm sao cho máy của Loli có lượng RAM là lớn nhất có thể.

Hỏi lượng RAM lớn nhất có thể là bao nhiêu?

Input

• Dòng đầu chứa số nguyên ~T\ (1\le T\le 50)~ là số lượng test nhỏ.
• Sau đó là các test nhỏ:
  • Dòng đầu của mỗi test nhỏ chứa hai số nguyên ~n~ và ~k~ ~(1\le n \le 5000,\ 1\le k\le 5000)~.
  • Dòng tiếp theo chứa ~n~ số nguyên ~a_i\ (1\le a_i\le 5000)~.
  • Dòng cuối cùng chứa ~n~ số nguyên ~b_i\ (1\le b_i\le 5000)~.

Output

• Mỗi dòng chứa một số nguyên là kết quả của test nhỏ tương ứng.

Sample Input 1

4
5 1
1 1 1 5 1
1 1 1 1 1
3 10
30 20 10
100 9 10
5 1
2 2 2 2 2
100 100 100 100 100
5 8
128 64 8 16 32
128 64 8 16 32

Sample Output 1

6
29
1
256

Giải thích

• Ở test nhỏ đầu tiên, sử dụng lần lượt phần mềm thứ ~1, 2, 3, 5~ để tăng lượng RAM thành ~5~ GB, sau đó dùng phần mềm ~4~ để tăng lên thành ~6~ GB.
• Ở test nhỏ thứ hai, Loli chỉ có đủ RAM để chạy phần mềm thứ ~3~, sau khi dùng nó, Loli sẽ có ~20~ GB RAM, đủ để chạy phần mềm thứ ~2~ để tăng lên thành ~29~ GB. Tuy nhiên phần mềm thứ ~1~ cần tới ~30~ GB RAM, vì vậy phần mềm thứ ~1~ không chạy được, đáp án cuối là ~29~ GB RAM.
• Ở test nhỏ thứ ba, mọi phần mềm đều cần hơn ~1~ GB RAM để chạy, vì vậy Loli không chạy được phần mềm nào, đáp án cuối là ~1~ GB RAM.

Ràng buộc

• 30% số điểm có ~n \le 10~.
• 40% số điểm có ~n \le 1000~.
• 30% số điểm còn lại không có ràng buộc gì thêm.

Sau những giờ code căng thẳng là những giờ giải trí bằng những bài toán hình.

Cho tam giác vuông ~ABC~ có ~\angle{B} = 90^\circ~. Ta có ~AC = 18\ (cm)~. Kẻ đường cao ~BH\ (H \in AC)~ có độ dài là ~x~ sao cho ~x~ thỏa mãn:

$$ x^2 - 51x + 279 = 0$$

Khi đó, diện tích lớn nhất có thể của tam giác ~ABC~ có thể được viết dưới dạng biểu thức ~\dfrac{a+b\sqrt{c}}{d}\ (cm^2)~ với ~a,b,c,d~ là những số nguyên, sao cho ước chung lớn nhất của ~(a,b,d)~ bằng ~1~, ~c~ không phải là bội của bất kỳ số chính phương nào trừ ~1~, và ~d~ là số nguyên tố.

Hãy tính tổng ~z\times a+(z+1)\times b+(z+2)\times c+(z+3)\times d~, với ~z~ là một số nguyên bất kỳ nhập từ đầu vào.

Input

• Một số nguyên duy nhất là số nguyên ~z~ ~(|z| \le 10^9)~.

Output

• Một số nguyên là tổng ~z\times a+(z+1)\times b+(z+2)\times c+(z+3)\times d~.

Loli đang tổ chức một giải Liên Quân cực kỳ hoành tráng. Trên vũ trụ này có ~N~ đội thi đấu chuyên nghiệp. Giải đấu "Arena of Loli" của chúng ta chỉ quy tụ ~K~ đội tuyển trong số ~N~ đội ~(K \le N)~, họ đến từ bốn biển năm châu sáu thế giới, từ Sài gòn Ăn tôm, Hộp Chơi Game cho đến Tia chớp...

Tuy nhiên, nếu mời các đội lệch quá nhiều về trình độ thì sẽ không công bằng chút nào. Bằng nhiều tiêu chí khác nhau, Loli đánh giá sức mạnh của một đội là một số nguyên dương ~A_i~. Ta có khoảng cách trình độ của một cặp đấu bao gồm hai đội tuyển ~i~ và ~j~ bất kỳ là ~|A_i - A_j|\ (i \neq j)~.

Loli muốn bạn chọn ra ~K~ đội trong số ~N~ đội sao cho tổng khoảng cách trình độ giữa mọi cặp đấu trong ~K~ đội được chọn là bé nhất có thể.

Input

• Dòng đầu tiên là hai số ~N~ và ~K~ ~(2 ≤ K ≤ N ≤ 10^5)~.
• Dòng tiếp theo là dãy chỉ số sức mạnh ~A~ gồm ~N~ số nguyên dương ~(1 ≤ A_i ≤ 10^5)~.

Output

• In ra một số là tổng bé nhất có thể.

Sample Input 1

4 3
1 2 3 99

Sample Output 1

4

Sample Input 2

28 7
370 216 570 975 62 225 521 790 915 485 114 538 59 849 418 990 319 681 948 127 408 652 34 88 612 856 526 208

Sample Output 2

1420

Giải thích

• Ở test đầu tiên, khi chọn ~3~ đội đầu tiên, ta có tổng chênh lệch là ~|1 - 2| + |1 - 3| + |2 - 3| = 4~, là tổng chênh lệch thấp nhất có thể.

Ma trận bình phương là một bài toán đơn giản và giải trí mà Loli mới tìm hiểu. Chi tiết bài toán như sau:

• Cho một số nguyên dương ~N~.
• Ta phải dựng một ma trận ~N \times N~ gồm các số nguyên trong khoảng ~[1; 10^8]~ sao cho tổng của bình phương các số mỗi hàng và mỗi cột là một số chính phương.
• Hai hàng bất kỳ không được giống nhau (tuy nhiên hai cột bất kỳ vẫn có thể giống nhau).
• Hai hàng ~i~ và ~j~ được coi là giống nhau khi ~A_{ik} = A_{jk}~ với ~\forall k \in [1;N]~.

Loli dù đạt 10 phẩy toán nhưng vẫn phải bó tay trước bài toán đơn giản và giải trí này. Hãy giúp Loli dựng một ma trận bình phương thỏa mãn.

Input

• Gồm một dòng ghi số ~N\ (1 ≤ N ≤ 200)~.

Output

• In ra ma trận ~N\times N~ thỏa mãn, các số trong một dòng viết cách nhau bằng một dấu cách.
• Nếu có nhiều phuơng án thỏa mãn, in ra một phương án bất kì. Luôn đảm bảo có ít nhất một phương án thỏa mãn.

Sample Input 1

3

Sample Output 1

2 1 2
1 2 2
2 2 1

Giải thích

Mỗi hàng và cột đều bao gồm hai số ~2~ và một số ~1~. Tổng các bình phương một hàng hoặc cột bất kỳ trong cách trên là ~2^2 + 2^2 + 1^2 = 9~.

~9~ là một số chính phương nên thỏa mãn yêu cầu đề bài.

Ràng buộc

• 30% số điểm có ~N \le 5~.
• 20% số điểm có ~N \le 10~.
• 25% số điểm có ~N \le 20~.
• 25% số điểm còn lại không có ràng buộc gì thêm.