Problem: Dark Assembly is a governing body in the Netherworld. Here sit the senators who take the most important decisions for the player. For example, to expand the range of the shop or to improve certain characteristics of the character the Dark Assembly's approval is needed.

The Dark Assembly consists of n senators. Each of them is characterized by his level and loyalty to the player. The level is a positive integer which reflects a senator's strength. Loyalty is the probability of a positive decision in the voting, which is measured as a percentage with precision of up to 10%. 

Senators make decisions by voting. Each of them makes a positive or negative decision in accordance with their loyalty. If strictly more than half of the senators take a positive decision, the player's proposal is approved. 

If the player's proposal is not approved after the voting, then the player may appeal against the decision of the Dark Assembly. To do that, player needs to kill all the senators that voted against (there's nothing wrong in killing senators, they will resurrect later and will treat the player even worse). The probability that a player will be able to kill a certain group of senators is equal to A / (A + B), where A is the sum of levels of all player's characters and B is the sum of levels of all senators in this group. If the player kills all undesired senators, then his proposal is approved.

Senators are very fond of sweets. They can be bribed by giving them candies. For each received candy a senator increases his loyalty to the player by 10%. It's worth to mention that loyalty cannot exceed 100%. The player can take no more than k sweets to the courtroom. Candies should be given to the senators before the start of voting.

Determine the probability that the Dark Assembly approves the player's proposal if the candies are distributed among the senators in the optimal way.

Input

The first line contains three integers n, k and A (1 ≤ n, k ≤ 8, 1 ≤ A ≤ 9999).

Then n lines follow. The i-th of them contains two numbers — bi and li — the i-th senator's level and his loyalty.

The levels of all senators are integers in range from 1 to 9999 (inclusive). The loyalties of all senators are integers in range from 0 to 100 (inclusive) and all of them are divisible by 10.

Output

Print one real number with precision 10 - 6 — the maximal possible probability that the Dark Assembly approves the player's proposal for the best possible distribution of candies among the senators.

Examples

Input

5 6 100
11 80
14 90
23 70
80 30
153 70


Output

1.0000000000


Input

5 3 100
11 80
14 90
23 70
80 30
153 70


Output

0.9628442962


Input

1 3 20
20 20


Output

0.7500000000

Note

In the first sample the best way of candies' distribution is giving them to first three of the senators. It ensures most of votes.

It the second sample player should give all three candies to the fifth senator.

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.*;
import static java.lang.Math.*;

public class Main{
    
    public void go(){
        int n=sc.nextInt(), k=sc.nextInt(), A=sc.nextInt();
        ArrayList< ArrayList< Integer > > waysGiveCandies = doit1(n, k, new ArrayList< Integer >());
/*
        System.out.printf("%d\n", waysGiveCandies.size());
        for(ArrayList< Integer > x : waysGiveCandies){
            for(int i : x)
                System.out.printf("%d ", i);
            System.out.printf("\n");
        }
*/
        int[] lvl = new int[n], loyal = new int[n];
        for(int i=0; i<n; ++i){
            lvl[i] = sc.nextInt();
            loyal[i] = sc.nextInt();
        }

        double ret = 0;
        for(ArrayList< Integer > distribution : waysGiveCandies){
            double[] Loyal = new double[n];
            for(int i=0; i<n; ++i) Loyal[i] = min(loyal[i]+10*distribution.get(i), 100)/100.0;
            double pWin = 0;
            for(int i=0; i<1<<n; ++i){
                double pVoteOccurs = 1;
                for(int j=0; j<n; ++j) 
                    if((i&(1<<j))!=0) // if winner
                        pVoteOccurs *= Loyal[j];
                    else // if loser
                        pVoteOccurs *= 1-Loyal[j];

                int B = 0;
                for(int j=0; j<n; ++j) if((i&(1<<j))==0)
                    B += lvl[j];
                double pWinFight = (double)A/(A+B);

                // if win vote, don't need to fight
                if(bit_count(i)*2 > n)
                    pWinFight = 1;

                pWin += pVoteOccurs * pWinFight;
            }
            ret = max(ret, pWin);
        }

        System.out.printf("%.9f\n", ret);
    }

    ArrayList< ArrayList< Integer > > doit1(int n, int k, ArrayList< Integer > soFar){
        ArrayList< ArrayList< Integer > > ret = new ArrayList< ArrayList< Integer > >();
        
        // base case
        if(n==1){
            soFar.add(k);
            ret.add(soFar);
            return ret;
        }

        // general case
        for(int i=0; i<k+1; ++i){
            ArrayList< Integer > tmp = new ArrayList< Integer >(soFar);
            tmp.add(i);
            ret.addAll(doit1(n-1, k-i, tmp));
        }

        return ret;
    }

    // syntax
    // ArrayList<Integer>[] myMat = (ArrayList<Integer>[]) new ArrayList[nB];

    // Pairs
    public class ii implements Comparable< ii >{
        int x, y;
        public ii(){}
        public ii(int xx, int yy){ x=xx; y=yy; }
        public int compareTo(ii p){ return x!=p.x ? x-p.x : y-p.y; }
        public int hashCode(){ return 31*x+y; }
        public boolean equals(Object o){
            if(!(o instanceof ii)) return false;
            ii p = (ii) o;
            return x==p.x && y==p.y;
        }
        public String toString(){ return "("+x+", "+y+")"; }
    }
/*
    public class pair< X extends Comparable< X >,Y extends Comparable< Y > > implements Comparable< pair< X,Y > >{
        X x;
        Y y;
        public pair(){}
        public pair(X xx, Y yy){ x=xx; y=yy; }
        public int compareTo(pair< X,Y > p){ return x.compareTo(p.x)!=0 ? x.compareTo(p.x) : y.compareTo(p.y); }
        public int hashCode(){ return 31*x.hashCode()+y.hashCode(); }
        public boolean equals(Object o){
            if((o.getClass() != this.getClass())) return false;
            pair< X,Y > p = (pair< X,Y >) o;
            return x.equals(p.x) && y.equals(p.y);
        }
        public String toString(){ return "("+x+", "+y+")"; }
    }
*/
    // my stuff
    public static final int INF = 1000*1000*1000+7;
    public static final double EPS = 1e-9;
    public static final double PI = 2*acos(0.0);
    public void rev(Object[] a){ for(int i=0; i<a.length/2; ++i){ Object t=a[i]; a[i]=a[a.length-1-i]; a[a.length-1-i]=t; } }
    public void rev(int[] a){ for(int i=0; i<a.length/2; ++i){ int t=a[i]; a[i]=a[a.length-1-i]; a[a.length-1-i]=t; } }
    public int bit_count(long x){ return x==0 ? 0 : 1+bit_count(x&(x-1)); }
    public int low_bit(int x){ return x&-x; } // 0011 0100 returns 0000 0100
    public int sign(int x){ return x<0 ? -1 : x>0 ? 1 : 0; }
    public int sign(double x){ return x<-EPS ? -1 : x>EPS ? 1 : 0; }
    int[] unpack(ArrayList< Integer > a){
        int[] ret = new int[a.size()];
        for(int i=0; i<a.size(); ++i) ret[i] = a.get(i);
        return ret;
    }

    // generic main stuff
    static myScanner sc;
    static PrintWriter pw;
    static long startTime;
    public static void main(String[] args) throws Exception{
        // sc = new Scanner(System.in);
        sc = (new Main()).new myScanner(new BufferedReader(new InputStreamReader(System.in)));
        pw = new PrintWriter(System.out);
        startTime = System.nanoTime();
        (new Main()).go();
        // errprintln("nanoTime="+(System.nanoTime()-startTime)/1000000/1000.0);
        pw.flush();
        System.exit(0);
    }

    // capable of reading   2.86M 6dp doubles per second
    //                      2.16M 12dp doubles per second
    //                      2.75M int per second
    public class myScanner{
        private BufferedReader f;
        private StringTokenizer st;
        public myScanner(BufferedReader ff){ f=ff; st=new StringTokenizer(""); }
        public int nextInt(){ return Integer.parseInt(nextToken()); }
        public double nextDouble(){ return Double.parseDouble(nextToken()); }
        public String nextLine(){
            st=new StringTokenizer("");
            String ret="";
            try{ ret=f.readLine(); }catch(Exception e){}
            return ret;
        }
        public String nextToken(){
            while(!st.hasMoreTokens()) try{ st=new StringTokenizer(f.readLine()); } catch(Exception e){}
            return st.nextToken();
        }
    }


}