Petya studies in a school and he adores Maths. His class has been studying arithmetic expressions. On the last class the teacher wrote three positive integersa, b,c on the blackboard. The task was to insert signs of operations ‘+‘ and ‘*‘, and probably brackets between the numbers so that the value of the resulting expression is as large as possible. Let‘s consider an example: assume that the teacher wrote numbers 1, 2 and 3 on the blackboard. Here are some ways of placing signs and brackets:

• 1+2*3=7
• 1*(2+3)=5
• 1*2*3=6
• (1+2)*3=9

Note that you can insert operation signs only betweena and b, and betweenb and c, that is, you cannot swap integers. For instance, in the given sample you cannot get expression (1+3)*2.

It‘s easy to see that the maximum value that you can obtain is 9.

Your task is: given a,b and c print the maximum value that you can get.

The input contains three integers a, b and c, each on a single line (1?≤?a,?b,?c?≤?10).

Print the maximum value of the expression that you can obtain.

As you know, all the kids in Berland love playing with cubes. Little Petya hasn towers consisting of cubes of the same size. Tower with numberi consists of a_i cubes stacked one on top of the other. Petya defines theinstability of a set of towers as a value equal to the difference between the heights of the highest and the lowest of the towers. For example, if Petya built five cube towers with heights (8, 3, 2, 6, 3), the instability of this set is equal to 6 (the highest tower has height 8, the lowest one has height 2).

The boy wants the instability of his set of towers to be as low as possible. All he can do is to perform the following operation several times: take the top cube from some tower and put it on top of some other tower of his set. Please note that Petya would never put the cube on the same tower from which it was removed because he thinks it‘s a waste of time.

Before going to school, the boy will have time to perform no more thank such operations. Petya does not want to be late for class, so you have to help him accomplish this task.

The first line contains two space-separated positive integersn and k (1?≤?n?≤?100,1?≤?k?≤?1000) — the number of towers in the given set and the maximum number of operations Petya can perform. The second line containsn space-separated positive integers a_i (1?≤?a_i?≤?10⁴) — the towers‘ initial heights.

In the first line print two space-separated non-negative integerss and m (m?≤?k). The first number is the value of the minimum possible instability that can be obtained after performing at mostk operations, the second number is the number of operations needed for that.

In the next m lines print the description of each operation as two positive integersi and j, each of them lies within limits from1 to n. They represent that Petya took the top cube from thei-th tower and put in on the j-th one (i?≠?j). Note that in the process of performing operations the heights of some towers can become equal to zero.

If there are multiple correct sequences at which the minimum possible instability is achieved, you are allowed to print any of them.

In the first sample you need to move the cubes two times, from the second tower to the third one and from the second one to the first one. Then the heights of the towers are all the same and equal to 6.

分析：分能否整除两种情况，每操作一次就排一次序，因为n不大，不会超时，要特判n=1和a[i]都相等的情况

<span style="font-size:14px;">#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 1005;
struct Info
{
    int h;
    int pos;
}info[MAX];
int re[5000];

int cmp(Info a, Info b)
{
    return a.h < b.h;
}

int main()
{
    memset(re, 0, sizeof(re));
    int n, k, sum = 0, ave = 0, mod = 0;
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        info[i].pos = i;
        scanf("%d", &info[i].h);
        sum += info[i].h;
    }
    sort(info + 1, info + n + 1, cmp);
    mod = sum % n;
    ave = sum / n;
    int tmp = 0;
    int cnt = 0;
    int cnt2 = 0;
    int ma = info[n].h - info[1].h;
    if(n == 1 || ma == 0)
    {
        printf("0 0\n");
        return 0;
    }
    while(1)
    {
        if(mod != 0)
        {
            k--;
            cnt2++;
            info[n].h--;
            info[1].h++;
            re[cnt++] = info[n].pos;
            re[cnt++] = info[1].pos;
            sort(info + 1, info + n + 1, cmp);
            ma = min(ma, info[n].h - info[1].h);
            if(ma == 1 || k == 0)
                break;
        }
        else
        {
            k--;
            cnt2++;
            info[n].h--;
            info[1].h++;
            re[cnt++] = info[n].pos;
            re[cnt++] = info[1].pos;
            sort(info + 1, info + n + 1, cmp);
            ma = min(ma, info[n].h - info[1].h);
            if(ma == 0 || k == 0)
                break;
        }
    }
    printf("%d %d\n", ma, cnt2);
    for(int i = 0; i < cnt - 1; i += 2)
        printf("%d %d\n", re[i], re[i+1]);
}
</span>

3
5 2
3 1
4 2

2

3
6 1
5 2
4 3

6