Cost of array

3.8

6 votes
Ad-Hoc, Swap, Medium-Hard, Approximate
Problem

Given two length-n arrays a and b, we define the score by the dot product between them, i.e., ni=1aibi. 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,SSC). You want to maximize this score.

Input

The first line contains one number n (1n218).

The second line contains n numbers - a1,a2,a3,,an (0ai<m).

The third line contains n numbers - b1,b2,b3,,bn (0bi<230).

The fourth line contains one number m (1m512).

The next m lines contains m integers representing the matrix cost[i][j] (0cost[i][j]<230,cost[i][i]=0,cost[i][j]=cost[j][i]).

Output

The first line contains one number k (0k220) - 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,SSC). 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 0bi<210 (1in).

Sample Input
3
2 1 0
1 2 3
3
0 1 1
1 0 1
1 1 0
Sample Output
1
1 3
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

You swap indices 1 and 3 with cost 1 and obtain the final sequence [0,1,2]. The final score score is max(0,841)=3.

Editor Image

?