Let's define a generalized cover time of a graph G with n vertices (numbered 0 through $n-1$) as the expected value of the length of a random walk that starts in vertex 0 and stops immediately after marking each vertex at least once. Each time vertex v is visited by a random walk, it is marked with probability $p_v$. In other words, the following algorithm is performed:

• define current vertex v; initially $v=0$

• define the set of marked vertices S; initially $S = \left\lbrace 0 \right\rbrace$ with probability $p_0$ and is empty with probability $1-p_0$

• while S does not contain all vertices:

  • select an edge e randomly uniformly among all edges incident to v

  • denote the other endpoint of e (different from v) as u

  • u becomes the current vertex v and with probability $p_u$ it's added to the set S

The length of this walk is the number of times the body of the loop is executed plus one (equal to the number of visited vertices).

You are given two integers $n,k$, two sequences of length n, $d_0, d_1, \ldots, d_{n-1}$ and $p_0, p_1, \ldots, p_{n-1}$, and a matrix w of size $n \times n$ such that $w_{i,j}$ represents the cost of connecting vertices i and j with an undirected edge,

Construct an undirected graph G with n vertices such that for each $0 \le i \lt n$, vertex i has degree equal to $d_i$ and the sum of costs of edges in the graph is as most k. The objective is to minimize the generalized cover time on this graph.

The resulting graph has to be connected. The graph must not contain loops (i.e. edges from a vertex to itself), but it may contain multiple edges between the same pair of vertices.

Constraints

• $1 \leq n \leq 100$
• $1 \leq d_i \leq n$ for each $0 \le i \lt n$
• $\sum\limits_{i=0}^{n-1} d_i$ is even
• $0.2 \leq p_i \leq 1$ and has exactly 2 decimal places
• $1 \leq w_{i,j} \leq 1000$
• $w_{i,i} = 0$ and $w_{i,j} = w_{j,i}$
• $1 \leq k \leq 10^7$
• it's guaranteed that at least one connected graph with n vertices corresponding to the given degree sequence and the total cost of edges at most k exists

Input format

In the first line of the input, there is a single integer n.

In the second line, there are n space-separated integers $d_0, d_1, \ldots, d_{n-1}$.

In the third line, there are n space-separated floating point numbers $p_0, p_1, \ldots, p_{n-1}$, each given with exactly 2 decimal places.

After that, n lines follow. The i-th of them constains n space-separated integers $w_{i,0}, w_{i_1}, \ldots, w_{i,n-1}$.

The last line contains a single integer k.

Output format

In the first line, print one integer m denoting the number of edges in the graph.

Then, print m lines. In the i-th of these lines, print two space-separated integers $u_i$ and $v_i$ ($0 \leq u_i, v_i \lt n$) denoting an edge between vertices $u_i$ and $v_i$ in the graph.

Test case generation

Each test file has manually assigned values of n, k, and ranges $[mind, maxd]$, $[minp, maxp]$, $[minw, maxw]$. A sequence $f_0, f_1, \ldots, f_{n-1}$ will be drawn randomly independently from the uniform integer distribution over the range $[mind, maxd]$. Next, the sequence $d_0, d_1, \ldots, d_{n-1}$ is generated from $f_0, f_1, \ldots, f_{n-1}$ using the expected_degree_graph function (without self-loops) from the Python networkx module. Next, values of $p_i$ for $0 \le i \lt n$ and $w_{i,j}$ for $0 \le i < j \lt n$ are all generated independently from uniform distributions $[minp, maxp]$ and $[minw, maxw]$ respectively.

Value of k is generated as follows. First, 100 graphs are generated using mentioned above expected_degree_graph function for the previously generated sequence f. Then, for each of these graphs, we compute the sum of its edges according to the previously generated $w_{i,j}$ weight function. These sums are sorted and the one with rank 50 in this sorted sequence is chosen as the value of k.

Scoring

For each test file, the checker will take the graph generated by your program, run the random walk algorithm described at the beginning of the problem statement $W=1000$ times and compute the average of their lengths; let's denote this average by X. This value will be used as an approximation of the generated cover time of the graph. The random walks will be generated using a fixed seed for each test file.

If $X \ge 2 \cdot 10^4$, the verdict of your submission for the given test file will be Wrong Answer. Otherwise, the score of your submission will be $X^2 \cdot \frac{1}{n} \cdot \sum\limits_{i=0}^{n-1} p_i$.

During the contest, every submission will be evaluated on $50$ test files. The total score for a submission is the sum of the scores for all test files. The goal is to minimize the total score.

After the contest, every submission will be re-evaluated on $100$ test files. This set will be generated using the method described above in the following way: for each test in the test set used during the contest, two tests generated with the same parameters (but not necessarily the same seed) will appear in this final test set. The final score of your solution will be its total score on these $100$ test files.