Given two length-n arrays a and b, we define the score by the dot product between them, i.e., ∑ni=1ai∗bi. The original score is denoted as S.
You can apply at most 220 swaps to modify the array a. The cost of swaping ax and ay is cost[ax][ay]. The total cost is denoted as C.
After your swaps, we can recompute the score again, denoted as S. The final score is max(0,S′−S−C). You want to maximize this score.
Input
The first line contains one number n (1≤n≤218).
The second line contains n numbers - a1,a2,a3,…,an (0≤ai<m).
The third line contains n numbers - b1,b2,b3,…,bn (0≤bi<230).
The fourth line contains one number m (1≤m≤512).
The next m lines contains m integers representing the matrix cost[i][j] (0≤cost[i][j]<230,cost[i][i]=0,cost[i][j]=cost[j][i]).
Output
The first line contains one number k (0≤k≤220) - the number of swaps.
The next k lines contains two numbers separated by space ui,vi - signifying that at step i you will swap values aui,avi
Scoring
The final score is max(0,S′−S−C). You want to maximize this score.
Tests
The will be in total 100 tests with 4 types of generation:
1. m=512.
2. m=512 and 70% of values in matrix cost are smaller than 210.
3. m=64.
4. m=512 and 0≤bi<210 (1≤i≤n).
You swap indices 1 and 3 with cost 1 and obtain the final sequence [0,1,2]. The final score score is max(0,8−4−1)=3.