Sereja and Order
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja have N programs. Sereja should run every program on two computers. Program number i works A[i] seconds on first computer and B[i] seconds on second. On each computer Sereja isn't able to run two programs in parallel, also Sereja isn't able to run one program on two computers in one moment. Sereja need to run all programs on both computers in minimal time. Help Sereja in his problem.
First line contain integer T number of test cases. T tests follow. First line of each test case contain integer N. Next N lines contain integers A[i], B[i].
For each test case output optimal time in separated line. On the next N lines. In i-th line output pair of numbers X, Y X - start of working program number i on first computer, j - the same information for second computer.
- 1 ≤ Sum of N over all the test cases ≤ 200000
- 1 ≤ N ≤ 10000
- 1 ≤ A[i], B[i] ≤ 100000
Input: 2 1 1 1 3 2 2 1 1 1 1 Output: 2 0 1 4 2 0 0 2 1 3 .
|Tags||hard, nov14, sereja|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.