Một công ty có \(n\) nhân viên và có \(n\) nhiệm vụ cần phải được thực hiện. Chúng ta biết đối với mỗi nhân viên chi phí để thực hiện từng nhiệm vụ. Mỗi nhân viên nên được giao cho chính xác một nhiệm vụ. Tổng chi phí tối thiểu là bao nhiêu nếu chúng ta phân công các nhiệm vụ một cách tối ưu và bằng cách nào nào chúng có thể được giao?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng nhân viên và số lượng nhiệm vụ cần phải thực hiện.
• Sau này, có \(n\) dòng, mỗi dòng bao gồm \(n\) số nguyên. Dòng thứ \(i\) bao gồm các số nguyên \(c_{i1},c_{i2},\ldots,c_{in}\): chi phí của mỗi nhiệm vụ khi nó được giao cho nhân viên thứ \(i\).

Output

• Đầu tiên in tổng chi phí tối thiểu.
• Sau đó in \(n\) dòng mỗi dòng bao gồm hai số nguyên \(a\) và \(b\): bạn giao nhiệm vụ thứ \(b\) cho nhân viên thứ \(a\).
• Nếu có nhiều giải pháp, bạn có thể in bất kỳ giải pháp nào trong số đó.

Constraints

• \(1 \leq n \leq 200\)
• \(1 \leq c_{ij} \leq 1000\)

Example

Sample input

4
17 8 16 9
7 15 12 19
6 9 10 11
14 7 13 10

Sample output

33
1 4
2 1
3 3
4 2

Note

Tổng chi phí tối thiểu là \(33\). Chúng ta có thể làm được điều này bằng cách giao cho nhân viên \(1\) nhiệm vụ \(4\), nhân viên \(2\) nhiệm vụ \(1\), nhân viên \(3\) nhiệm vụ \(3\) và nhân viên \(4\) nhiệm vụ \(2\). Điều này sẽ tốn \(9 + 7 + 10 + 7 = 33\).