0193. Black-White Numbers

Input file name:	black.in
Output file name:	black.out
Time limit:	500 ms
Memory limit:	32 megabytes

You are given white integer numbers W_i (1 ≤ i ≤ n) and black integer numbers B_i (1 ≤ i ≤ n). Write a program which finds such 2n positive integers k_i and l_i (1 ≤ i ≤ n) that k_i ≠ k_j∀i ≠ j, l_i ≠ l_j∀i ≠ j, 1 ≤ k_i, l_i ≤ n, A=Σ_{1 ≤ i ≤ n} |W_ki-B_li| will be minimal possible.

Input file

There is a single integer n (1 ≤ n ≤ 10000) on the first line. The second line contains n integers – white numbers. The third line contains n integer black numbers. All numbers do not exceed 2,000,000,000 by absolute value.

Output file

Write to the output n+1 lines. In the first line you are to write out minimal possible value of A. In the next n lines write out 2n positive integers: (i+1)-th line must contain k_i and l_i, separated by a single space.

Examples:

black.in	black.out
1 1 2	1 1 1

Source: Petrozavodsk Summer 2003. Saratov SU Contest, Wednesday, August 27

Discuss       Submit a solution



Printable version