Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P194PROH - Problem H - Tiệc lẩu của momo

Momo vừa trở lại Tokyo, và quyết định mở tiệc lẩu với hai người bạn thân của mình là Yamato và Ao!

Tất nhiên, muốn món lẩu ngon thì nước lẩu cũng phải hoàn hảo. Và momo hiểu rất rõ điều này nên chị bắt tay ngay vào việc.

Vừa quay lại Tokyo từ nhà nên momo có rất nhiều nguyên liệu - chính xác là chị có n loại nguyên liệu khác nhau để chế biến nước lẩu.

Cách mà momo chế biến nước lẩu như sau:

Đầu tiên, chị chọn k (2 ≤ k ≤ n) nguyên liệu khác nhau trong số n nguyên liệu của mình theo thứ tự x1, x2, …, xk (1 ≤ xi ≤ n, 1 ≤ i ≤ k). Sau đó, chị sẽ sử dụng lần lượt các nguyên liệu từ x1, x2, …, cho tới xk để chế biến nước lẩu theo cách của mình.

Độ hài lòng của Yamato và Ao đối với “sản phẩm” thu được được tính toán rất phức tạp:

  • Sự xuất hiện của nguyên liệu thứ i sẽ tăng độ hài lòng của Yamato thêm byi đơn vị và tăng độ hài lòng của Ao thêm bai đơn vị.
  • Nếu nguyên liệu thứ j được sử dụng ngay sau nguyên liệu thứ i, độ hài lòng của Yamato tăng thêm cy(i,j) đơn vị và độ hài lòng của Ao tăng thêm ca(i,j) đơn vị.

Tuy nhiên, vốn là những nguyên liệu lạ mua từ Ottawa, nên không phải thứ gì Yamato và Ao cũng đều thích cả. Momo cần phải chọn nguyên liệu và cách chế biến thích hợp sao cho độ hài lòng của hai người ít chênh lệch nhất, và nếu có nhiều cách thực hiện thì phải chọn cách để độ hài lòng của cả hai là lớn nhất!

Bạn có thể giúp chị đại của chúng ta có được một công thức hoàn hảo nhất để thỏa mãn cả hai người bạn của mình hay không? 

Input

Bắt đầu mỗi file input là một dòng chứa một số nguyên T chỉ số bộ test (1 ≤ T ≤ 30).

Mỗi bộ test sẽ có dạng như sau:

Dòng đầu tiên chứa một số nguyên n (2 ≤ n ≤ 10) - số loại nguyên liệu mà momo có.

Dòng thứ hai chứa n số nguyên by1, by2, ..., byn (0 ≤ | by| ≤ 10) - độ hài lòng của Yamato khi từng nguyên liệu được sử dụng.

Dòng thứ ba chứa n số nguyên ba1, ba2, ..., ban (0 ≤ | ba| ≤ 10) - độ hài lòng của Ao khi từng nguyên liệu được sử dụng.

n dòng tiếp theo, dòng thứ i gồm n số nguyên cy(i,1), cy(i,2), ..., cy(i,n) (0 ≤ | cy(i,j) | ≤ 10) - độ hài lòng của Yamato khi từng nguyên liệu được dùng ngay sau nguyên liệu thứ i.

n dòng tiếp nữa, dòng thứ i gồm n số nguyên ca(i,1), ca(i,2), ..., ca(i,n) (0 ≤ | ca(i,j) | ≤ 10) - độ hài lòng của Ao khi từng nguyên liệu được dùng ngay sau nguyên liệu thứ i.

Output

Mỗi bộ test sẽ có output như sau:

Dòng đầu tiên chứa một số nguyên M - số cặp giá trị độ hài lòng tối ưu khác nhau.

M dòng tiếp theo, mỗi dòng in ra 2 số nguyên Y, A - lần lượt là độ hài lòng của Yamato và Ao.

M dòng này được sắp xếp theo thứ tự sau: độ hài lòng của Yamato tăng dần; nếu hai cặp giá trị có cùng độ hài lòng của Yamato thì cặp giá trị mà độ hài lòng của Ao nhỏ hơn sẽ được in ra trước.

Example

Input
1
3
2 2 -4
2 2 -4
0 1 0
3 0 0
0 0 0
0 3 8
1 0 8
8 8 0

Output
2
5 7
7 5

Giải thích:

Ta sẽ thử mọi công thức mà momo có thể thực hiện:

Công thức 1: (1) → (2) → (3). => (Y, A) = (2 + 2 – 4 + 1 + 0, 2 + 2 – 4 + 3 + 8) = (1, 11).

Công thức 2: (1) → (3) → (2). => (Y, A) = (2 – 4 + 2 + 0 + 0, 2 – 4 + 2 + 8 + 8) = (0, 16).

Công thức 3: (2) → (1) → (3). => (Y, A) = (2 + 2 – 4 + 3 + 0, 2 + 2 – 4 + 1 + 8) = (3, 9).

Công thức 4: (2) → (3) → (1). => (Y, A) = (2 – 4 + 2 + 0 + 0, 2 – 4 + 2 + 8 + 8) = (0, 16).

Công thức 5: (3) → (1) → (2). => (Y, A) = (-4 + 2 + 2 + 0 + 1, -4 + 2 + 2 + 8 + 3) = (1, 11).

Công thức 6: (3) → (2) → (1). => (Y, A) = (-4 + 2 + 2 + 0 + 3, -4 + 2 + 2 + 8 + 1) = (3, 9).

Công thức 7: (1) → (2). => (Y, A) = (2 + 2 + 1, 2 + 2 + 3) = (5, 7).

Công thức 8: (1) → (3). => (Y, A) = (2 – 4 + 0 , 2 – 4 + 8) = (-2, 6).

Công thức 9: (2) → (1). => (Y, A) = (2 + 2 + 3, 2 + 2 + 1) = (7, 5).

Công thức 10: (2) → (3). => (Y, A) = (2 – 4 + 0, 2 – 4 + 8) = (-2, 6).

Công thức 11: (3) → (1). => (Y, A) = (-4 + 2 + 0, -4 + 2 + 8) = (-2, 6).

Công thức 12: (3) → (2). => (Y, A) = (-4 + 2 + 0, -4 + 2 + 8) = (-2, 6).

Từ đây ta thấy, hai trường hợp tối ưu nhất là công thức 7 và công thức 9, khi độ hài lòng của Yamato và Ao hoặc bằng 5 hoặc bằng 7.


Được gửi lên bởi:adm
Ngày:2019-03-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.