Problem: The rabbit, who successfully defeated the ambushed enemy, succeeded in advancing the hero into the enemy's castle. When the hero released the cats trapped in the castle dungeon, some of them were the hero's. It will help me.

According to the cats, to reach the Demon King in the back of the castle, you will have to go through n rooms from 1 to n in this order, but one enemy is waiting in each room and you will defeat them one by one. For each of the m cats that became friends, the winning rate against each enemy in each room is known, and the main character dispatches these cats one by one to the back of the castle. Each room Can only pass after defeating the enemy there, so if one cat is killed by an enemy in one room, the next cat will fight from the enemy in that room.

The dispatched cat will proceed until it is killed by the enemy, but each time you know which room the dispatched cat was killed by the enemy, you can decide which cat to dispatch next. For example, will the cats have the greatest chance of defeating all the enemies awaiting them?



Input

The first line of input is given with m and n separated by spaces. 1 ≤ m, n ≤ 16

The next m line is given n real numbers that represent the probability that the cat will beat the enemy. The jth real number in the i + 1st line represents the probability that the cat will beat the enemy in room j. Is up to 3 digits after the decimal point.

Output

Answer the probability when you decide the order so that the cats have the maximum probability of defeating all the enemies waiting for them. The output may contain errors, but the error from the true value is 10-9. Within.

Example

Input

2 3
0.900 0.500 0.100
0.500 0.500 0.500


Output

0.372500000000

Solution (in CPP):

Solution:
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <valarray>
//cin.sync_with_stdio(false);
//streambuf
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using ti3 = tuple<int, int, int>;
using vti3 = vector<ti3>;
template<class T, int s>using va = vector<array<T, s>>;
template<class T, class T2> using umap = unordered_map<T, T2>;
template<class T> using uset = unordered_set<T>;
template<class T, class S> void cmin(T &a,S&&b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a,S&&b) { if (a < b)a = b; }
#define ALL(a) a.begin(),a.end()
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a) for(int i=1;i<=a;i++)
#define rrep(i,a) for(int i=a-1;i>=0;i--)
#define rrep1(i,a) for(int i=a;i;i--)
const ll mod = 1000000007;
#ifndef INT_MAX
const int INT_MAX = numeric_limits<signed>().max();
#endif
template<class T>using heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>using pque = priority_queue<T, vector<T>, function<T(T, T)>>;
template <class T>
inline void hash_combine(size_t & seed, const T & v) {
	hash<T> hasher;
	seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
namespace std {

	template<typename S, typename T> struct hash<pair<S, T>> {
		inline size_t operator()(const pair<S, T> & v) const {
			size_t seed = 0;
			hash_combine(seed, v.first);
			hash_combine(seed, v.second);
			return seed;
		}
	};
	// Recursive template code derived from Matthieu M.
	template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
	struct HashValueImpl
	{
		static void apply(size_t& seed, Tuple const& tuple)
		{
			HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
			hash_combine(seed, std::get<Index>(tuple));
		}
	};

	template <class Tuple>
	struct HashValueImpl<Tuple, 0>
	{
		static void apply(size_t& seed, Tuple const& tuple)
		{
			hash_combine(seed, std::get<0>(tuple));
		}
	};

	template <typename ... TT>
	struct hash<std::tuple<TT...>>
	{
		size_t
			operator()(std::tuple<TT...> const& tt) const
		{
			size_t seed = 0;
			HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
			return seed;
		}

	};
}
ull pow(ull base, ull i, ull mod) {
	ull a = 1;
	while (i) {
		if (i & 1) {
			a *= base;
			a %= mod;
		}
		base *= base;
		base %= mod;
		i /= 2;
	}
	return a;
}
class unionfind {
	vector<int> par, rank, size_;//????????§??????????????¢???????????????????????????rank???????????????size?????????
public:
	unionfind(int n) :par(n), rank(n), size_(n, 1) {
		iota(ALL(par), 0);
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y)return;
		if (rank[x] < rank[y])swap(x, y);
		par[y] = x;
		size_[x] += size_[y];
		if (rank[x] == rank[y])rank[x]++;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return size_[find(x)];
	}
};
ll gcd(ll a, ll b) {
	while (b) {
		ll c = a%b;
		a = b;
		b = c;
	}
	return a;
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b)*b;
}
int popcnt(unsigned long long a) {
	a = (a & 0x5555555555555555) + (a >> 1 & 0x5555555555555555);
	a = (a & 0x3333333333333333) + (a >> 2 & 0x3333333333333333);
	a = (a & 0x0f0f0f0f0f0f0f0f) + (a >> 4 & 0x0f0f0f0f0f0f0f0f);
	a = (a & 0x00ff00ff00ff00ff) + (a >> 8 & 0x00ff00ff00ff00ff);
	a = (a & 0x0000ffff0000ffff) + (a >> 16 & 0x0000ffff0000ffff);
	return (a & 0xffffffff) + (a >> 32);
}
template<class T,const T& updater(const T&,const T&)>
class segtree {
	vector<T> obj;
	int offset;
	T e;
	int bufsize(int num) {
		int i = 1;
		for (; num >i; i <<= 1);
		offset = i - 1;
		return (i << 1) - 1;
	}
	T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)return e;
		if (a <= l && r <= b)return obj[k];
		else return updater(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
	}
public:
	T query(int a, int b) {//[a,b)
		return query(a, b, 0, 0, offset + 1);
	}
	void updateall(int l = 0, int r = -1) {
		if (r < 0)r = offset;
		else r--;
		l += offset, r += offset;
		do {
			l = l - 1 >> 1, r = r - 1 >> 1;
			for (int i = l; i < r; i++)obj[i] = updater(obj[i * 2 + 1], obj[i * 2 + 2]);
		} while (r);
	}
	void update(int k, T &&a) {
		k += offset;
		obj[k] = a;
		while (k) {
			k = k - 1 >> 1;
			obj[k] = updater(obj[k * 2 + 1], obj[k * 2 + 2]);
		}
	}
	segtree(int n, T e) :obj(bufsize(n), e), e(e) {}
	segtree(vector<T> &vec, T e) :obj(bufsize(vec.size()), e), e(e){
		copy(vec.begin(), vec.end(), obj.begin() + offset);
		updateall();
	}
	typename vector<T>::reference operator[](int n) {
		return obj[n + offset];
	}
};
template<class T>
class matrix {
	vector<vector<T>> obj;
	pair<int, int> s;
public:
	matrix(pair<int, int> size, T e = 0) :matrix(size.first, size.second, e) {}
	matrix(int n, int m = -1, T e = 0) :obj(n, vector<T>(m == -1 ? n : m, e)), s(n, m == -1 ? n : m) {}
	static matrix e(int n) {
		matrix a = (n);
		for (int i = 0; i < n; i++)a[i][i] = 1;
		return a;
	}
	matrix& operator+=(const matrix &p) {
		if (s != p.s)throw runtime_error("matrix error");
		for (int i = 0; i < s.first; i++)
			for (int j = 0; j < s.second; j++)obj[i][j] += p.obj[i][j];
		return *this;
	}
	matrix operator+(const matrix &p) {
		matrix res(*this);
		return res += p;
	}
	matrix& operator-=(const matrix &p) {
		if (s != p.s)throw runtime_error("matrix error");
		for (int i = 0; i < s.first; i++)
			for (int j = 0; j < s.second; j++)obj[i][j] -= p.obj[i][j];
		return *this;
	}
	matrix operator-(const matrix &p) {
		matrix res(*this);
		return res -= p;
	}
	matrix& operator*=(T p) {
		for (auto &a : obj)
			for (auto &b : a)b *= p;
		return *this;
	}
	matrix operator*(T p) {
		matrix res(*this);
		return res *= p;
	}
	matrix operator*(const matrix &p) {
		if (s.second != p.s.first)throw runtime_error("matrix error");
		matrix ret(s.first, p.s.second);
		for (int i = 0; i < s.first; i++)
			for (int j = 0; j < s.second; j++)
				for (int k = 0; k < p.s.second; k++)ret[i][k] += obj[i][j] * p.obj[j][k];
		return ret;
	}
	matrix &operator*=(const matrix &p) {
		return *this = *this*p;
	}
	pair<int, int> size() const {
		return s;
	}
	matrix &mod(T m) {
		if (m < 0)
			for (auto &a : obj)
				for (auto &b : a)b = (b ? 1 : 0);
		else for (auto &a : obj)
			for (auto &b : a)b %= m;
		return *this;
	}
	typename vector<vector<T>>::reference operator[](int t) {
		return obj[t];
	}
};
template<class T> inline
matrix<T> pow(matrix<T> &base, unsigned exp) {
	auto base_(base);
	if (base_.size().first != base_.size().second)throw runtime_error("matrix error");
	matrix<T> res = matrix<T>::e(base_.size().first);
	for (;;) {
		if (exp & 1)res *= base_;
		if (!(exp /= 2))break;
		base_ *= base_;
	}
	return res;
}
template<class T> inline
matrix<T> modpow(matrix<T> &base, unsigned exp, T m) {
	auto base_(base);
	if (base.size().first != base_.size().second)throw runtime_error("matrix error");
	matrix<T> res = matrix<T>::e(base_.size().first);
	for (;;) {
		if (exp & 1)(res *= base_).mod(m);
		if (!(exp /= 2))break;
		(base_ *= base_).mod(m);
	}
	return res;
}
template<class T>int id(vector<T> &a, T b) {
	return lower_bound(ALL(a), b) - a.begin();
}
class Flow {
	int V;
	struct edge { int to, cap, rev, cost; };
	vector<vector<edge>> G;
	vector<int> level, iter, h, dist, prevv, preve;
	Flow(int size) :G(size + 1), V(size + 1) {
	}
	void add_edge(int from, int to, int cap, int cost = 0) {
		G[from].push_back(edge{ to, cap, (int)G[to].size(),cost });
		G[to].push_back(edge{ from,0,(int)G[from].size() - 1,-cost });
	}
	void bfs(int s) {
		fill(level.begin(), level.end(), -1);
		queue<int> que;
		level[s] = 0;
		que.push(s);
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (int i = 0; i < G[v].size(); i++) {
				edge &e = G[v][i];
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					que.push(e.to);
				}
			}
		}
	}
	int dfs(int v, int t, int f) {
		if (v == t)return f;
		for (int &i = iter[v]; i < G[v].size(); i++) {
			edge &e = G[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	int max_flow(int s, int t) {
		level.resize(V);
		iter.resize(V);
		int flow = 0;
		for (;;) {
			bfs(s);
			if (level[t] < 0)return flow;
			fill(iter.begin(), iter.end(), 0);
			int f;
			while ((f = dfs(s, t, numeric_limits<int>::max()))>0) {
				flow += f;
			}
		}
	}
	typedef pair<int, int> P;
	int min_cost_flow(int s, int t, int f) {
		int res = 0;
		h.resize(V);
		dist.resize(V);
		prevv.resize(V);
		preve.resize(V);
		fill(h.begin(), h.end(), 0);
		while (f > 0) {
			priority_queue<P, vector<P>, greater<P>> que;
			fill(dist.begin(), dist.end(), numeric_limits<int>::max());
			dist[s] = 0;
			que.push({ 0,s });
			while (!que.empty()) {
				P p = que.top(); que.pop();
				int v = p.second;
				if (dist[v] < p.first)continue;
				for (int i = 0; i < G[v].size(); i++) {
					edge &e = G[v][i];
					if (e.cap > 0 && dist[e.to]>dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						que.push({ dist[e.to],e.to });
					}
				}
			}
			if (dist[t] == numeric_limits<int>::max()) {
				return -1;
			}
			for (int v = 0; v < V; v++)h[v] += dist[v];

			int d = f;
			for (int v = t; v != s; v = prevv[v]) {
				d = min(d, G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d*h[t];
			for (int v = t; v != s; v = prevv[v]) {
				edge &e = G[prevv[v]][preve[v]];
				e.cap -= d;
				G[v][e.rev].cap += d;
			}
		}
		return res;
	}
};

// Suffix Array	?????????O(|S|log^2|S|), ????´¢O(|T|log|S|), ?????????????§????O(|S|)
class StringSearch {
	const int n;
	string S;
public:
	vector<int> sa, rank;
	StringSearch(const string &S_)
		: n(S_.size()), S(S_), sa(n + 1), rank(n + 1)
	{
		for (int i = 0; i <= n; i++) {
			sa[i] = i;
			rank[i] = i < n ? S[i] : -1;
		}

		vector<int> tmp(n + 1);
		for (int k = 1; k <= n; k *= 2) {
			auto Compare_SA = [=](int i, int j) {
				if (this->rank[i] != this->rank[j]) return this->rank[i] < this->rank[j];

				int ri = i + k <= n ? this->rank[i + k] : -1;
				int rj = j + k <= n ? this->rank[j + k] : -1;
				return ri < rj;
			};
			sort(sa.begin(), sa.end(), Compare_SA);

			tmp[sa[0]] = 0;
			for (int i = 1; i <= n; i++) {
				tmp[sa[i]] = tmp[sa[i - 1]] + (Compare_SA(sa[i - 1], sa[i]) ? 1 : 0);
			}
			for (int i = 0; i <= n; i++) {
				this->rank[i] = tmp[i];
			}
		}
	}

	bool Contain(const string &T) {
		int a = 0, b = n;
		while (b - a > 1) {
			int c = (a + b) / 2;
			if (S.compare(sa[c], T.length(), T) < 0) a = c;
			else b = c;
		}
		return S.compare(sa[b], T.length(), T) == 0;
	}

	vector<int> LCPArray() {
		for (int i = 0; i <= n; i++) rank[sa[i]] = i;

		int h = 0;
		vector<int> lcp(n + 1);
		for (int i = 0; i < n; i++) {
			int j = sa[rank[i] - 1];

			if (h > 0) h--;
			for (; j + h < n && i + h < n; h++) {
				if (S[j + h] != S[i + h]) break;
			}
			lcp[rank[i] - 1] = h;
		}
		return lcp;
	}
};
double dp[17][1 << 16];
double p[16][16];
int main() {
	int m, n;
	cin >> m >> n;
	rep(i, m)rep(j, n)cin >> p[j][i];
	fill(dp[n], dp[n + 1], 1);
	rrep(i, n) {
		rep(j, 1 << m) {
			double x = 0;
			rep(k, m) {
				if (j & 1 << k) {
					double t = 0, pass = 1;
					for (int l = i; l < n; l++) {
						t += dp[l][j&~(1 << k)] * pass*(1 - p[l][k]);
						pass *= p[l][k];
					}
					t += dp[n][j&~(1 << k)] * pass;
					cmax(x, t);
				}
			}
			dp[i][j] = x;
		}
	}
	cout << fixed<<setprecision(100) << dp[0][(1 << m) - 1] << endl;
}