Problem: You are going to work in Codeforces as an intern in a team of n engineers, numbered 1 through n. You want to give each engineer a souvenir: a T-shirt from your country (T-shirts are highly desirable in Codeforces). Unfortunately you don't know the size of the T-shirt each engineer fits in. There are m different sizes, numbered 1 through m, and each engineer will fit in a T-shirt of exactly one size.

You don't know the engineers' exact sizes, so you asked your friend, Gerald. Unfortunately, he wasn't able to obtain the exact sizes either, but he managed to obtain for each engineer i and for all sizes j, the probability that the size of the T-shirt that fits engineer i is j.

Since you're planning to give each engineer one T-shirt, you are going to bring with you exactly n T-shirts. For those n T-shirts, you can bring any combination of sizes (you can bring multiple T-shirts with the same size too!). You don't know the sizes of T-shirts for each engineer when deciding what sizes to bring, so you have to pick this combination based only on the probabilities given by your friend, Gerald. 

Your task is to maximize the expected number of engineers that receive a T-shirt of his size. 

This is defined more formally as follows. When you finally arrive at the office, you will ask each engineer his T-shirt size. Then, if you still have a T-shirt of that size, you will give him one of them. Otherwise, you don't give him a T-shirt. You will ask the engineers in order starting from engineer 1, then engineer 2, and so on until engineer n.

Input

The first line contains two space-separated integers n and m (1 ≤ n ≤ 3000, 1 ≤ m ≤ 300), denoting the number of engineers and the number of T-shirt sizes, respectively.

Then n lines follow, each line contains m space-separated integers. The j-th integer in the i-th line represents the probability that the i-th engineer fits in a T-shirt of size j. Each probability will be given as an integer between 0 and 1000, inclusive. The actual probability should be calculated as the given number divided by 1000. 

It is guaranteed that for any engineer, the sum of the probabilities for all m T-shirts is equal to one.

Output

Print a single real number denoting the maximum possible expected number of engineers that will receive a T-shirt.

For the answer the absolute or relative error of 10 - 9 is acceptable.

Examples

Input

2 2
500 500
500 500


Output

1.500000000000


Input

3 3
1000 0 0
1000 0 0
0 1000 0


Output

3.000000000000


Input

1 4
100 200 300 400


Output

0.400000000000

Note

For the first example, bring one T-shirt of each size. With 0.5 chance, either both engineers fit inside T-shirts of size 1 or both fit inside T-shirts of size 2. With the other 0.5 chance, one engineer fits inside a T-shirt of size 1 and the other inside a T-shirt of size 2. If the first is true, the number of engineers that receive a T-shirt is one. If the second is true, the number of such engineers is two. Hence, the expected number of engineers who receive a T-shirt is 1.5. This is maximum possible expected number of engineers for all sets of T-shirts. 

For the second example, bring two T-shirts of size 1 and one T-shirt of size 2. This way, each engineer will definitely receive a T-shirt of his size.

For the third example, bring one T-shirt of size 4.

Solution (in JAVA):

Solution:
//package croc.Final;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class D2 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni(), m = ni();
		double[][] P = new double[n][m];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				P[i][j] = (double)ni() / 1000;
			}
		}
		
		Queue<double[]> q = new PriorityQueue<double[]>(m+1, new Comparator<double[]>(){
			public int compare(double[] a, double[] b){
				return -(int)Math.signum(a[1]- b[1]);
			}
		});
		
		dps = new double[m][n+1];
		for(int i = 0;i < m;i++){
			Arrays.fill(dps[i], 1);
		}
		
		for(int i = 0;i < m;i++){
			q.add(new double[]{i, calc(P, i)});
		}
		
		int[] ct = new int[m];
		double E = 0;
		for(int i = 0;i < n;i++){
			double[] d = q.poll();
			int ind = (int)d[0];
			ct[ind]++;
			E += d[1];
			d[1] = calc(P, ind);
			q.add(d);
		}
		out.printf("%.9f\n", E);
	}
	
	double[][] dps;
	
	// k種類目のTシャツのs個目が貰われる確率
	double calc(double[][] P, int k)
	{
		int n = P.length;
		double[] dp = new double[n+1];
		for(int i = 1;i <= n;i++){
			dp[i] = dps[k][i-1] * P[i-1][k] + dp[i-1];
			dps[k][i] -= dp[i];
		}
		dps[k] = dp;
//		tr(dp);
		return dp[n];
	}
	
	void run() throws Exception
	{
		is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception
	{
		new D2().run();
	}
	
	public int ni()
	{
		try {
			int num = 0;
			boolean minus = false;
			while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
			if(num == '-'){
				num = 0;
				minus = true;
			}else{
				num -= '0';
			}
			
			while(true){
				int b = is.read();
				if(b >= '0' && b <= '9'){
					num = num * 10 + (b - '0');
				}else{
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}
	
	public long nl()
	{
		try {
			long num = 0;
			boolean minus = false;
			while((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));
			if(num == '-'){
				num = 0;
				minus = true;
			}else{
				num -= '0';
			}
			
			while(true){
				int b = is.read();
				if(b >= '0' && b <= '9'){
					num = num * 10 + (b - '0');
				}else{
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}
	
	public String ns()
	{
		try{
			int b = 0;
			StringBuilder sb = new StringBuilder();
			while((b = is.read()) != -1 && (b == '\r' || b == '\n' || b == ' '));
			if(b == -1)return "";
			sb.append((char)b);
			while(true){
				b = is.read();
				if(b == -1)return sb.toString();
				if(b == '\r' || b == '\n' || b == ' ')return sb.toString();
				sb.append((char)b);
			}
		} catch (IOException e) {
		}
		return "";
	}
	
	public char[] ns(int n)
	{
		char[] buf = new char[n];
		try{
			int b = 0, p = 0;
			while((b = is.read()) != -1 && (b == ' ' || b == '\r' || b == '\n'));
			if(b == -1)return null;
			buf[p++] = (char)b;
			while(p < n){
				b = is.read();
				if(b == -1 || b == ' ' || b == '\r' || b == '\n')break;
				buf[p++] = (char)b;
			}
			return Arrays.copyOf(buf, p);
		} catch (IOException e) {
		}
		return null;
	}
	
	
	double nd() { return Double.parseDouble(ns()); }
	boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}