One day Polycarpus stopped by a supermarket on his way home. It turns out that the supermarket is having a special offer for stools. The offer is as follows: if a customer's shopping cart contains at least one stool, the customer gets a 50% discount on the cheapest item in the cart (that is, it becomes two times cheaper). If there are several items with the same minimum price, the discount is available for only one of them!

Polycarpus has k carts, and he wants to buy up all stools and pencils from the supermarket. Help him distribute the stools and the pencils among the shopping carts, so that the items' total price (including the discounts) is the least possible.

Polycarpus must use all k carts to purchase the items, no shopping cart can remain empty. Each shopping cart can contain an arbitrary number of stools and/or pencils.

Input

The first input line contains two integers n and k (1 ≤ k ≤ n ≤ 103) — the number of items in the supermarket and the number of carts, correspondingly. Next n lines describe the items as "ci ti" (without the quotes), where ci (1 ≤ ci ≤ 109) is an integer denoting the price of the i-th item, ti (1 ≤ ti ≤ 2) is an integer representing the type of item i (1 for a stool and 2 for a pencil). The numbers in the lines are separated by single spaces.

Output

In the first line print a single real number with exactly one  decimal place — the minimum total price of the items, including the discounts.

In the following k lines print the descriptions of the items in the carts. In the i-th line print the description of the i-th cart as "t b1 b2 ... bt" (without the quotes), where t is the number of items in the i-th cart, and the sequence b1, b2, ..., bt (1 ≤ bj ≤ n) gives the indices of items to put in this cart in the optimal distribution. All indices of items in all carts should be pairwise different, each item must belong to exactly one cart. You can print the items in carts and the carts themselves in any order. The items are numbered from 1 to n in the order in which they are specified in the input.

If there are multiple optimal distributions, you are allowed to print any of them.

Examples

Input

3 2
2 1
3 2
3 1


Output

5.5
2 1 2
1 3


Input

4 3
4 1
1 2
2 2
3 2


Output

8.0
1 1
2 4 2
1 3

Note

In the first sample case the first cart should contain the 1st and 2nd items, and the second cart should contain the 3rd item. This way each cart has a stool and each cart has a 50% discount for the cheapest item. The total price of all items will be: 2·0.5 + (3 + 3·0.5) = 1 + 4.5 = 5.5.
11 11
6 2
6 2
1 2
2 2
3 1
6 2
1 1
1 1
3 1
3 1
6 2
 21 7
14 1
882797755 2
17 1
906492329 2
209923513 2
802927469 2
949195463 2
677323647 2
2129083 2
2 1
13 1
539523264 2
7 1
8 1
12 1
363470241 2
9838294 2
18716193 2
30 1
17 1
24 1
 1 1
1 1
 10 1
28 1
1 2
1 2
1 2
15 1
16 1
22 1
20 1
1 2
1 2
 1 1
1 2
 10 1
1 1
2 2
1 1
23 2
17 2
1 1
1 1
30 2
1 1
9 2
 4 3
4 1
1 2
2 2
3 2
 5 4
24 1
19 1
28 2
7 1
23 2
 5 4
10 1
10 1
10 1
9 1
5 2
 7 4
10 1
10 1
10 1
9 1
2 1
5 2
3 2
 7 5
10 1
10 1
10 1
9 1
4 1
5 2
3 2
 20 3
28 1
786180179 2
16 1
617105650 2
23 1
21 1
22 1
7 1
314215182 2
409797301 2
14 1
993310357 2
372545570 2
791297014 2
13 1
25 1
307921408 2
625842662 2
136238241 2
13 1
 7 4
10 1
10 1
10 1
9 1
4 1
5 2
3 2
 21 21
42856481 2
562905883 2
942536731 2
206667673 2
451074408 2
27 1
29 1
172761267 2
23 1
24 1
106235116 2
126463249 2
29 1
9 1
83859496 2
5 1
25 1
337838080 2
109402491 2
5 1
24 1

32.5
1 10
1 9
1 5
1 8
1 7
1 11
1 6
1 2
1 1
1 4
1 3
 5362337336.5
1 19 
1 21 
1 3 
1 20 
1 1 
1 11 
15 15 14 13 10 7 4 2 6 8 12 16 5 18 17 9 
 0.5
1 1 
 105.5
10 1 7 8 6 5 2 3 4 9 10 
 1.0
1 1 
 85.5
10 1 3 6 7 9 2 10 5 4 8 
 8.0
1 1 
1 2 
2 3 4 
 76.0
1 1 
1 2 
1 4 
2 3 5 
 26.5
1 3 
1 2 
1 1 
2 4 5 
 33.0
1 3 
1 2 
1 1 
4 4 5 6 7 
 30.0
1 3 
1 2 
1 1 
1 4 
3 5 6 7 
 5354453716.0
1 1 
1 16 
18 5 7 6 3 11 15 20 8 12 14 2 18 4 10 13 9 17 19 
 34.5
1 3 
1 2 
1 1 
4 4 5 6 7 
 3142600975.0
1 13
1 7
1 6
1 17
1 21
1 10
1 9
1 14
1 20
1 16
1 3
1 2
1 5
1 18
1 4
1 8
1 12
1 19
1 11
1 15
1 1

import static java.lang.Math.*;
import java.util.*;
import java.io.*;

public class B {

    class Item implements Comparable<Item> {
        int price, idx;
        public int compareTo(Item arg0) {
            return -price+arg0.price;
        }
        public String toString() {
            return idx+" "+price;
        }
    }
    
    public void solve() throws Exception {
        
        int n = nextInt(), k = nextInt();
        int[] p1 = new int[n], p2 = new int[n]; 
        int cnt1 = 0;
        for (int i=0; i<n; ++i) {
            int p = nextInt(), type = nextInt();
            if (type==1) {
                cnt1++;
                p1[i] = p;
            } else p2[i] = p;
        }
        
        Item[] it1 = new Item[cnt1];
        Item[] it2 = new Item[n-cnt1];
        
        int pos = 0;
        for (int i=0; i<n; ++i) if (p1[i]!=0) {
            it1[pos] = new Item();
            it1[pos].idx = i+1;
            it1[pos++].price = p1[i];
        }
        pos = 0;
        for (int i=0; i<n; ++i) if (p2[i]!=0) {
            it2[pos] = new Item();
            it2[pos].idx = i+1;
            it2[pos++].price = p2[i];
        }
        
        Arrays.sort(it1); Arrays.sort(it2);
//      debug(it1); debug(it2);
        
        int[][] ki = new int[k][1000];
        int[] kpos = new int[1000];
        
        int x = 0;
        for (int i=0; i<it1.length && i<k; ++i) {
            ki[i][kpos[i]++] = it1[i].idx;
            x++;
        }
        
        long tot = 0;
        for (int i=0; i<p2.length; ++i) tot += 2*p2[i];
        for (int i=0; i<p1.length; ++i) tot += 2*p1[i];
        for (int i=0; i<k-1 && i<cnt1; ++i) tot -= it1[i].price;
        int minLast = INF;
        for (int i=k-1; i<cnt1; ++i) minLast = min(minLast,it1[i].price);
        for (int i=0; i<it2.length; ++i) minLast = min(minLast,it2[i].price);
        if (cnt1>=k) tot -= minLast==INF ? 0:minLast;
        
        pos = min(k-1,x);
        int y = 0;
//      for (int i=0; i<k; ++i) {
//          print(kpos[i]+" ");
//          for (int j=0; j<kpos[i]; ++j) print(ki[i][j]+" ");
//          println();
//      }println("-------------");
        for (int i=0; i<n-x; ++i) {
            if (x<cnt1) {
                ki[pos][kpos[pos]++] = it1[x].idx;
                x++;
            } else {
                ki[pos][kpos[pos]++] = it2[y].idx;
                y++;
            }
            pos = min(pos+1,k-1);
        }
        
        println(tot%2==0 ? (tot/2)+".0":(tot/2)+".5");
        for (int i=0; i<k; ++i) {
            print(kpos[i]+" ");
            for (int j=0; j<kpos[i]; ++j) print(ki[i][j]+" ");
            println();
        }
        
        
    }

    

    ////////////////////////////////////////////////////////////////////////////
    
    boolean showDebug = true;
    static boolean useFiles = false;
    static String inFile = "input.txt";
    static String outFile = "output.txt";

    double EPS = 1e-7;
    int INF = Integer.MAX_VALUE;
    long INFL = Long.MAX_VALUE;
    double INFD = Double.MAX_VALUE;

    
    int absPos(int num) {
        return num<0 ? 0:num;
    }
    long absPos(long num) {
        return num<0 ? 0:num;
    }
    double absPos(double num) {
        return num<0 ? 0:num;
    }
    
    int min(int... nums) {
        int r = Integer.MAX_VALUE;
        for (int i: nums)
            if (i<r) r=i;
        return r;
    }
    int max(int... nums) {
        int r = Integer.MIN_VALUE;
        for (int i: nums)
            if (i>r) r=i;
        return r;
    }
    long minL(long... nums) {
        long r = Long.MAX_VALUE;
        for (long i: nums)
            if (i<r) r=i;
        return r;
    }
    long maxL(long... nums) {
        long r = Long.MIN_VALUE;
        for (long i: nums)
            if (i>r) r=i;
        return r;
    }
    double minD(double... nums) {
        double r = Double.MAX_VALUE;
        for (double i: nums)
            if (i<r) r=i;
        return r;
    }
    double maxD(double... nums) {
        double r = Double.MIN_VALUE;
        for (double i: nums)
            if (i>r) r=i;
        return r;
    }
    
    long sumArr(int[] arr) {
        long res = 0;
        for (int i: arr)
            res+=i;
        return res;
    }
    long sumArr(long[] arr) {
        long res = 0;
        for (long i: arr)
            res+=i;
        return res;
    }
    double sumArr(double[] arr) {
        double res = 0;
        for (double i: arr)
            res+=i;
        return res;
    }

    long partsFitCnt(long partSize, long wholeSize) {
        return (partSize+wholeSize-1)/partSize;
    }

    boolean odd(long num) {
        return (num&1)==1;
    }
    
    boolean hasBit(int num, int pos) {
        return (num&(1<<pos))>0;
    }

    long binpow(long a, int n) {
        long r = 1;
        while (n>0) {
            if ((n&1)!=0) r*=a;
            a*=a;
            n>>=1;
        }
        return r;
    }

    boolean isLetter(char c) {
        return (c>='a' && c<='z') || (c>='A' && c<='Z');
    }
    boolean isLowercase(char c) {
        return (c>='a' && c<='z');
    }
    boolean isUppercase(char c) {
        return (c>='A' && c<='Z');
    }
    boolean isDigit(char c) {
        return (c>='0' && c<='9');
    }
    
    boolean charIn(String chars, String s) {
        if (s==null) return false;
        if (chars==null || chars.equals("")) return true;
        for (int i=0; i<s.length(); ++i)
            for (int j=0; j<chars.length(); ++j)
                if (chars.charAt(j)==s.charAt(i)) return true;
        return false;
    }
    
    String stringn(String s, int n) {
        if (n<1 || s==null) return "";
        StringBuilder sb = new StringBuilder(s.length()*n);
        for (int i=0; i<n; ++i) sb.append(s);
        return sb.toString();
    }
    String str(Object o) {
        if (o==null) return "";
        return o.toString();
    }


    long timer = System.currentTimeMillis();
    void startTimer() {
        timer = System.currentTimeMillis();
    }
    void stopTimer() {
        System.err.println("time: "+(System.currentTimeMillis()-timer)/1000.0);
    }


    static class InputReader {
        private byte[] buf;
        private int bufPos = 0, bufLim = -1;
        private InputStream stream;
        public InputReader(InputStream stream, int size) {
            buf = new byte[size];
            this.stream = stream;
        }
        private void fillBuf() throws IOException {
            bufLim = stream.read(buf);
            bufPos = 0;
        }
        char read() throws IOException {
            if (bufPos>=bufLim) fillBuf(); 
            return (char)buf[bufPos++];
        }
        boolean hasInput() throws IOException {
            if (bufPos>=bufLim) fillBuf();
            return bufPos<bufLim;
        }
    }
    
    static InputReader inputReader;
    static BufferedWriter outputWriter;

    char nextChar() throws IOException {
        return inputReader.read();
    }
    char nextNonWhitespaceChar() throws IOException {
        char c = inputReader.read();
        while (c<=' ') c=inputReader.read();
        return c;
    }
    String nextWord() throws IOException {
        StringBuilder sb = new StringBuilder();
        char c = inputReader.read();
        while (c<=' ') c=inputReader.read();
        while (c>' ') {
            sb.append(c);
            c = inputReader.read();
        }
        return new String(sb);
    }
    String nextLine() throws IOException {
        StringBuilder sb = new StringBuilder();
        char c = inputReader.read();
        while (c<=' ') c=inputReader.read();
        while (c!='\n' && c!='\r') {
            sb.append(c);
            c = inputReader.read();
        }
        return new String(sb);
    }
    int nextInt() throws IOException {
        int r = 0;
        char c = nextNonWhitespaceChar();
        boolean neg = false;
        if (c=='-') neg=true;
        else r=c-48;
        c = nextChar();
        while (c>='0' && c<='9') {
            r*=10;
            r+=c-48;
            c=nextChar();
        }
        return neg ? -r:r;
    }
    long nextLong() throws IOException {
        long r = 0;
        char c = nextNonWhitespaceChar();
        boolean neg = false;
        if (c=='-') neg=true;
        else r = c-48;
        c = nextChar();
        while (c>='0' && c<='9') {
            r*=10L;
            r+=c-48L;
            c=nextChar();
        }
        return neg ? -r:r;
    }
    double nextDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(nextWord());
    }
    int[] nextArr(int size) throws NumberFormatException, IOException {
        int[] arr = new int[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextInt();
        return arr;
    }
    long[] nextArrL(int size) throws NumberFormatException, IOException {
        long[] arr = new long[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextLong();
        return arr;
    }
    double[] nextArrD(int size) throws NumberFormatException, IOException {
        double[] arr = new double[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextDouble();
        return arr;
    }
    String[] nextArrS(int size) throws NumberFormatException, IOException {
        String[] arr = new String[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextWord();
        return arr;
    }
    char[] nextArrCh(int size) throws IOException {
        char[] arr = new char[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextNonWhitespaceChar();
        return arr;
    }
    char[][] nextArrCh(int rows, int columns) throws IOException {
        char[][] arr = new char[rows][columns];
        for (int i=0; i<rows; ++i)
            for (int j=0; j<columns; ++j)
                arr[i][j] = nextNonWhitespaceChar();
        return arr;
    }
    char[][] nextArrChBorders(int rows, int columns, char border) throws IOException {
        char[][] arr = new char[rows+2][columns+2];
        for (int i=1; i<=rows; ++i)
            for (int j=1; j<=columns; ++j)
                arr[i][j] = nextNonWhitespaceChar();
        for (int i=0; i<columns+2; ++i) {
            arr[0][i] = border;
            arr[rows+1][i] = border;
        }
        for (int i=0; i<rows+2; ++i) {
            arr[i][0] = border;
            arr[i][columns+1] = border;
        }
        return arr;
    }

    void printf(String format, Object... args) throws IOException {
        outputWriter.write(String.format(format, args));
    }
    void print(Object o) throws IOException {
        outputWriter.write(o.toString());
    }
    void println(Object o) throws IOException {
        outputWriter.write(o.toString());
        outputWriter.newLine();
    }
    void print(Object... o) throws IOException {
        for (int i=0; i<o.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(o[i].toString());
        }
    }
    void println(Object... o) throws IOException {
        print(o);
        outputWriter.newLine();
    }
    void printn(Object o, int n) throws IOException {
        String s = o.toString();
        for (int i=0; i<n; ++i) {
            outputWriter.write(s);
            if (i!=n-1) outputWriter.write(' ');
        }
    }
    void printnln(Object o, int n) throws IOException {
        printn(o, n);
        outputWriter.newLine();
    }
    void printArr(int[] arr) throws IOException {
        for (int i=0; i<arr.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(Integer.toString(arr[i]));
        }
    }
    void printArr(long[] arr) throws IOException {
        for (int i=0; i<arr.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(Long.toString(arr[i]));
        }
    }
    void printArr(double[] arr) throws IOException {
        for (int i=0; i<arr.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(Double.toString(arr[i]));
        }
    }
    void printArr(String[] arr) throws IOException {
        for (int i=0; i<arr.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(arr[i]);
        }
    }
    void printArr(char[] arr) throws IOException {
        for (char c: arr) outputWriter.write(c);
    }
    void printlnArr(int[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void printlnArr(long[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void printlnArr(double[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void printlnArr(String[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void printlnArr(char[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void halt(Object... o) throws IOException {
        if (o.length!=0) println(o);
        outputWriter.flush(); outputWriter.close();
        System.exit(0);
    }
    
    void debug(Object... o) {
        if (showDebug) System.err.println(Arrays.deepToString(o));
    }


    public static void main(String[] args) throws Exception {
        Locale.setDefault(Locale.US);
        if (!useFiles) {
            inputReader = new InputReader(System.in, 1<<16);
            outputWriter = new BufferedWriter(new OutputStreamWriter(System.out), 1<<16);
        } else {
            inputReader = new InputReader(new FileInputStream(new File(inFile)), 1<<16);
            outputWriter = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(new File(outFile))), 1<<16);
        }
        new B().solve();
        outputWriter.flush(); outputWriter.close();
    }
}
