QTDIVIDE - One piece

One of DB and TN common interests is traveling. One day, they went to Grand Line and found One Piece !

The One Piece treasure has n gold coins (n is even). Both them like gold coins, but they evaluate them as different values. So they decided to divide those coins by following method :

DB and TN do n / 2 steps, at each step, DB choose 2 coins, TN takes the coin that she evaluates it greater, and DB take the rest coin.

Let’s help DB find how to take the maximum value at possible.

Input

First line : a single integer n (n is even) – the number of coins

Second line : n integers a1, a2, …, an. ai is the value of ith coin that TN evaluates.

Third line : n integers b1, b2, …, bn. bi is the value of ith coin that DB evaluates.

Output

First line : an integer S – the maximum value DB can take.

Last n / 2 lines : ith line contains two number x and y (1 ≤ x, y ≤ n), are the indexes of two
coins that DB choose on ith step. Each coin must be chose exact one time.

If there are multiple ways, just print any of them.

Constraints

2 ≤ n ≤ 500 000

1 ≤ ai ≤ 109

1 ≤ bi ≤ 109

Note that a1, a2, …, an are n distinct integers.

Example

Input:
6
6 10 11 18 5 14
1 7 6 12 15 1

Output: 
28
5 1
2 6
3 4

Warning: large Input/Output data, be careful with certain languages


Added by:Kata
Date:2015-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:VOI - Day 2

hide comments
2018-05-23 01:39:35
Good one for me!
2017-11-11 04:02:00
MONKEY D LUFFY :D
2015-04-12 10:55:07 super
Hahaha they found one piece
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.