Banana Merging Optimization

You are given n bananas. The i-th banana is described by a positive integer pair \( (a_i, k_i) \) where \(2\le k_i\le 10\). Initially, there are n piles; the i-th pile contains only the i-th banana.

You may merge any two different piles. When merging two piles, you must decide which one of the two piles will participate in the merge. For every banana that is in the participating pile, its size \(a_i\) is reduced to \(\frac{a_i}{k_i}\) (i.e. multiplied by \(\frac{1}{k_i}\)). The other pile remains intact. The two piles are then merged into one. You repeat this process until all bananas are merged into a single pile.

Your goal is to maximize the final total size of all bananas. Since finding the optimal merging strategy may be difficult, you only need to output a scheme that gets as close as possible to the best total sum. In other words, if a banana never participates in a merge, its size remains \(a_i\); if it participates exactly once, its final size becomes \(\frac{a_i}{k_i}\). Thus, one reasonable strategy is to choose one pile as the safe pile (which never participates in a merge) and merge every other pile with it, so that the final total sum is \[ a_r + \sum_{\substack{i=1 \\ i\neq r}}^n \frac{a_i}{k_i}, \] where \(r\) is the index of the safe pile. One common heuristic is to choose the banana with the maximum value of \(a_i\Bigl(1-\frac{1}{k_i}\Bigr)\) as the safe one.

Output Scheme: First, output the number of merge operations (n-1). Then, for each merge, output two integers \(u\) and \(v\) (1-indexed) in one line, meaning that you merge the pile containing banana \(u\) (which will suffer the reduction) with the pile containing banana \(v\) (which stays intact). The merges must be such that all piles are eventually merged into one.

inputFormat

The first line of the input contains an integer \(n\) (\(n \ge 2\)), the number of bananas.

Each of the following \(n\) lines contains two integers \(a_i\) and \(k_i\) representing the size and the reduction factor of the i-th banana.

outputFormat

Output the merging scheme as follows:

• The first line contains an integer \(m = n-1\), the number of merge operations.
• Each of the following \(m\) lines contains two integers \(u\) and \(v\) (separated by a space), indicating that in that merge operation, the pile containing banana \(u\) is merged into the pile containing banana \(v\). In this merge, only the bananas in pile \(u\) will have their sizes reduced (each size divided by its corresponding \(k_i\)).

sample

3
100 2
80 5
60 3

2
1 2
3 2