测试点信息

//P6787
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(LL i=Head[A];i;i=Next[i])
#define INF 0x7fffffff
using namespace std;
const LL MAXN=5e6+10;

struct Node {
    LL ID,Num,Link,Cnt;
}State[MAXN];
priority_queue<Node>Mine;
LL Total,Ans;

bool Comp(const Node &A, const Node &B) {
    return A.Num<B.Num;
}

bool operator < (const Node &A,const Node &B) {
    if(A.Cnt==B.Cnt) return A.Num>B.Num;
    return A.Cnt<B.Cnt;
}

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

signed main() {
    //File();
    scanf("%lld",&Total);
    FOR(i,1,Total) { scanf("%lld",&State[i].Num); }
    FOR(i,1,Total) { scanf("%lld",&State[i].Link); }
    for(int i=1; i<=Total; i++) State[i].ID=i;
    if(Total==2) {
        if(State[1].Link==-1 && State[2].Link==-1) { printf("%lld\n1 2\n",min(State[1].Num,State[2].Num)); }
        else printf("-1\n");
        return 0;
    }
    FOR(i,1,Total) { 
		if(State[i].Link!=-1) 
		State[State[i].Link].Cnt++; 
	}
    sort(State+1,State+Total+1,Comp);
    for(LL i=(Total>>1)+1;i<Total;i++) Mine.push(State[i]);
    if(Mine.top().Cnt==Total-2 && Mine.top().Link!=-1) { printf("-1\n"); return 0; }
    Mine.push(State[Total]);
    if(Mine.top().Cnt==Total-1) { printf("-1\n"); return 0; }
    Node Temp=Mine.top();
    bool Jud=false;
    FOR(i,1,(Total>>1)) if(Temp.ID!=State[i].Link) { Jud=true; }
    if(Jud) {
        BOR(i,(Total>>1),1) Ans+=1ll*((Total>>1)-i+1)*State[i].Num;
        printf("%lld\n",Ans);
        BOR(i,(Total>>1),1) {
            Temp=Mine.top();
            if(State[i].Link!=Temp.ID) { printf("%lld %lld\n",State[i].ID,Temp.ID); Mine.pop(); }
            else {
                Mine.pop();
                printf("%lld %lld\n",State[i].ID,Mine.top().ID);
                Mine.pop();
                Mine.push(Temp);
            }
        }
    } else {
        LL Loc;         
        for(Loc=(Total<<1)+1;Loc<=Total;Loc++) {
            if(State[Loc].Num<Temp.Num) {
                if(State[Loc].Link!=Temp.ID) break;
            }
            if(State[Loc].Num>Temp.Num) {
                if(Temp.Link!=State[Loc].ID) break;
            }
        }
        Ans+=min(State[Loc].Num,Temp.Num);
        BOR(i,(Total>>1)-1,1) Ans+=1ll*((Total>>1)-i+1)*State[i].Num;
        printf("%lld\n",Ans);
        printf("%lld %lld\n",Temp.ID,State[Loc].ID);
        Mine.pop();
        for(LL i=(Total>>1)-1,j=Total>>1;i>=1 && j<=Total;i--,j++) {
            if(j==Loc || State[j].Num==Temp.Num) j++;
            printf("%lld %lld\n",State[i].ID,State[j].ID);
        }
    }
    //fclose(stdin); fclose(stdout);
    system("pause");
    return 0;
}