Problem: It turns out that you are a great fan of rock band AC/PE. Peter learned that and started the following game: he plays the first song of the list of n songs of the group, and you have to find out the name of the song. After you tell the song name, Peter immediately plays the following song in order, and so on.

The i-th song of AC/PE has its recognizability pi. This means that if the song has not yet been recognized by you, you listen to it for exactly one more second and with probability of pi percent you recognize it and tell it's name. Otherwise you continue listening it. Note that you can only try to guess it only when it is integer number of seconds after the moment the song starts playing.

In all AC/PE songs the first words of chorus are the same as the title, so when you've heard the first ti seconds of i-th song and its chorus starts, you immediately guess its name for sure.

For example, in the song Highway To Red the chorus sounds pretty late, but the song has high recognizability. In the song Back In Blue, on the other hand, the words from the title sound close to the beginning of the song, but it's hard to name it before hearing those words. You can name both of these songs during a few more first seconds.

Determine the expected number songs of you will recognize if the game lasts for exactly T seconds (i. e. you can make the last guess on the second T, after that the game stops).

If all songs are recognized faster than in T seconds, the game stops after the last song is recognized.

Input

The first line of the input contains numbers n and T (1 ≤ n ≤ 5000, 1 ≤ T ≤ 5000), separated by a space. Next n lines contain pairs of numbers pi and ti (0 ≤ pi ≤ 100, 1 ≤ ti ≤ T). The songs are given in the same order as in Petya's list.

Output

Output a single number — the expected number of the number of songs you will recognize in T seconds. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Examples

Input

2 2
50 2
10 1


Output

1.500000000


Input

2 2
0 2
100 2


Output

1.000000000


Input

3 3
50 3
50 2
25 2


Output

1.687500000


Input

2 2
0 2
0 2


Output

1.000000000

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * #
 * 
 * @author pttrung
 */
public class B_Round_284_Div1 {

	public static long MOD = 1000000007;

	public static void main(String[] args) throws FileNotFoundException {
		// PrintWriter out = new PrintWriter(new FileOutputStream(new File(
		// "output.txt")));
		PrintWriter out = new PrintWriter(System.out);
		Scanner in = new Scanner();
		int n = in.nextInt();
		int T = in.nextInt();
		int[][] data = new int[n][2];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 2; j++) {
				data[i][j] = in.nextInt();
			}
		}
		// out.println(cal(0, 0, T, data));
		double[][] pre = new double[101][T + 1];
		double[][] pow = new double[101][T + 1];
		for (int i = 0; i < 101; i++) {
			double p = (double) i / 100;
			pow[i][0] = 1;
			for (int j = 1; j <= T; j++) {
				pre[i][j] = p + (1 - p) * (j != 1 ? pre[i][j - 1] : 0);
				pow[i][j] = p * pow[i][j - 1];
			}

		}
		double[][] dp = new double[2][T + 2];
		int index = 0;
		for (int i = n - 1; i >= 0; i--) {

			double p = (double) data[i][0] / 100;
			double other = i != 0 ? ((double) data[i - 1][0] / 100) : 1;
			for (int j = T - 1; j >= 0; j--) {
				if (j + data[i][1] <= T) {
					double need = pow[100 - data[i][0]][data[i][1] - 1];
					dp[index][j] = pre[data[i][0]][data[i][1] - 1]
							+ need
							+ p
							* (dp[1 - index][j + 1] - (need * dp[1 - index][j
									+ data[i][1]]))
							+ (need * (dp[1 - index][j + data[i][1]] - (1 - p)
									* dp[1 - index][j + data[i][1] + 1]));

				} else {
					int max = T - j;
					dp[index][j] = pre[data[i][0]][max]
							+ p
							* dp[1 - index][j + 1]
							- (pow[100 - data[i][0]][max] * p * dp[1 - index][j + max + 1]);

				}
				dp[index][j] += (1 - other) * dp[index][j + 1];

			}
			index = 1 - index;

			// System.out.println(Arrays.toString(nxt));

		}
		out.println(dp[1 - index][0]);
		out.close();
	}

	public static double pow(double v, int p) {
		// System.out.println(v);
		if (p == 0) {
			return 1;
		}
		double tmp = pow(v, p / 2);
		if (p % 2 == 0) {
			return tmp * tmp;
		} else {
			return tmp * tmp * v;
		}
	}

	public static double cal(int index, int time, int T, int[][] data) {
		if (index == data.length) {
			return 0;
		}
		if (time >= T) {
			return 0;
		}
		double result = 0;
		double p = (double) data[index][0] / 100;
		double last = 1;
		double total = 0;
		double rate = 1;
		for (int i = 1; i <= data[index][1] && time + i <= T; i++) {
			double v;
			if (i == data[index][1]) {
				v = last * (1 + cal(index + 1, time + i, T, data));
				total += last * cal(index + 1, time + i, T, data);
				rate = last;
			} else {
				v = p * last * (1 + cal(index + 1, time + i, T, data));
				rate = p * last;
				total += p * last * cal(index + 1, time + i, T, data);
			}

			result += v;
			last *= (1 - p);
		}
		if (time == 1 && index == 2) {
			System.out.println("CHeckkk " + total);
		}
		return result;
	}

	public static int[] KMP(String val) {
		int i = 0;
		int j = -1;
		int[] result = new int[val.length() + 1];
		result[0] = -1;
		while (i < val.length()) {
			while (j >= 0 && val.charAt(j) != val.charAt(i)) {
				j = result[j];
			}
			j++;
			i++;
			result[i] = j;
		}
		return result;

	}

	public static boolean nextPer(int[] data) {
		int i = data.length - 1;
		while (i > 0 && data[i] < data[i - 1]) {
			i--;
		}
		if (i == 0) {
			return false;
		}
		int j = data.length - 1;
		while (data[j] < data[i - 1]) {
			j--;
		}
		int temp = data[i - 1];
		data[i - 1] = data[j];
		data[j] = temp;
		Arrays.sort(data, i, data.length);
		return true;
	}

	public static int digit(long n) {
		int result = 0;
		while (n > 0) {
			n /= 10;
			result++;
		}
		return result;
	}

	public static double dist(long a, long b, long x, long y) {
		double val = (b - a) * (b - a) + (x - y) * (x - y);
		val = Math.sqrt(val);
		double other = x * x + a * a;
		other = Math.sqrt(other);
		return val + other;

	}

	public static class Point implements Comparable<Point> {

		int x, y;

		public Point(int start, int end) {
			this.x = start;
			this.y = end;
		}

		@Override
		public int hashCode() {
			int hash = 5;
			hash = 47 * hash + this.x;
			hash = 47 * hash + this.y;
			return hash;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj == null) {
				return false;
			}
			if (getClass() != obj.getClass()) {
				return false;
			}
			final Point other = (Point) obj;
			if (this.x != other.x) {
				return false;
			}
			if (this.y != other.y) {
				return false;
			}
			return true;
		}

		@Override
		public int compareTo(Point o) {
			return x - o.x;
		}
	}

	public static class FT {

		long[] data;

		FT(int n) {
			data = new long[n];
		}

		public void update(int index, long value) {
			while (index < data.length) {
				data[index] += value;
				index += (index & (-index));
			}
		}

		public long get(int index) {
			long result = 0;
			while (index > 0) {
				result += data[index];
				index -= (index & (-index));
			}
			return result;

		}
	}

	public static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}

	public static long pow(long a, long b) {
		if (b == 0) {
			return 1;
		}
		if (b == 1) {
			return a;
		}
		long val = pow(a, b / 2);
		if (b % 2 == 0) {
			return val * val % MOD;
		} else {
			return val * (val * a % MOD) % MOD;

		}
	}

	static class Scanner {

		BufferedReader br;
		StringTokenizer st;

		public Scanner() throws FileNotFoundException {
			// System.setOut(new PrintStream(new
			// BufferedOutputStream(System.out), true));
			br = new BufferedReader(new InputStreamReader(System.in));
			// br = new BufferedReader(new InputStreamReader(new
			// FileInputStream(new File("input.txt"))));
		}

		public String next() {

			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					throw new RuntimeException();
				}
			}
			return st.nextToken();
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String nextLine() {
			st = null;
			try {
				return br.readLine();
			} catch (Exception e) {
				throw new RuntimeException();
			}
		}

		public boolean endLine() {
			try {
				String next = br.readLine();
				while (next != null && next.trim().isEmpty()) {
					next = br.readLine();
				}
				if (next == null) {
					return true;
				}
				st = new StringTokenizer(next);
				return st.hasMoreTokens();
			} catch (Exception e) {
				throw new RuntimeException();
			}
		}
	}
}