ADDED   SRM/790-U/1A.cpp
Index: SRM/790-U/1A.cpp
==================================================================
--- SRM/790-U/1A.cpp
+++ SRM/790-U/1A.cpp
@@ -0,0 +1,204 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <tuple>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+struct UnionFind
+{
+	vector<int> uf, sz;
+	int nc;
+
+	UnionFind(int N) : uf(N), sz(N, 1), nc(N)
+	{
+		for (int i = 0; i<N; ++i) uf[i] = i;
+	}
+	int size()
+	{
+		return nc;
+	}
+	int size(int a)
+	{
+		return sz[Find(a)];
+	}
+	int Find(int a)
+	{
+		return uf[a] == a ? a : uf[a] = Find(uf[a]);
+	}
+	// Semi-compression w.o. recursion.
+	//{ while(uf[a] != a) a=uf[a]=uf[uf[a]]; return a; }
+	bool Union(int a, int b)
+	{
+		a = Find(a);
+		b = Find(b);
+		if (a != b)
+		{
+			if (sz[a] >= sz[b]) swap(a, b);
+			uf[a] = b;
+			sz[b] += sz[a];
+			--nc;
+		}
+		return (a != b);
+	}
+};
+
+static const unsigned MODVAL = 1000000007;
+struct mint
+{
+	unsigned val;
+	mint() :val(0) {}
+	mint(int      x) :val(x%MODVAL) {}
+	mint(unsigned x) :val(x%MODVAL) {}
+	mint(LL       x) :val(x%MODVAL) {}
+};
+mint& operator+=(mint& x, mint y) { return x = x.val + y.val; }
+mint& operator-=(mint& x, mint y) { return x = x.val - y.val + MODVAL; }
+mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
+mint operator+(mint x, mint y) { return x += y; }
+mint operator-(mint x, mint y) { return x -= y; }
+mint operator*(mint x, mint y) { return x *= y; }
+
+mint POW(mint x, LL e) { mint v = 1; for (; e; x *= x, e >>= 1) if (e & 1) v *= x; return v; }
+
+class TheSocialNetwork { public:
+	int minimumCut(int n, int m, vector <int> u, vector <int> v, vector <int> l)
+	{
+		vector<tuple<int, int, int>> e;
+		for (int i = 0; i < m; ++i)
+			e.emplace_back(l[i], u[i]-1, v[i]-1);
+		sort(e.begin(), e.end());
+
+		vector<bool> use(m, false);
+		for (int k = e.size() - 1; k >= 0; --k) {
+			use[k] = true;
+			if (is_connected(n, m, use, e))
+				use[k] = false;
+		}
+
+		mint ans = 0;
+		for (int i = 0; i < m; ++i) if (!use[i])
+			ans += POW(2, get<0>(e[i]));
+		return ans.val;
+	}
+
+	bool is_connected(int n, int m, const vector<bool>& use, const vector<tuple<int, int, int>>& e) {
+		UnionFind uf(n);
+		for (int i = 0; i < m; ++i) if (use[i])
+			uf.Union(get<1>(e[i]), get<2>(e[i]));
+		return uf.size() == 1;
+
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const int& Expected, const int& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, TheSocialNetwork().minimumCut(n, m, u, v, l));}
+int main(){
+
+CASE(0)
+	int n = 6; 
+	int m = 6; 
+	int u_[] = {1, 2, 3, 4, 5, 6}	;
+	  vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 
+	int v_[] = {2, 3, 4, 5, 6, 1};
+	  vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 
+	int l_[] = {1, 7, 3, 4, 6, 12};
+	  vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 
+	int _ = 10; 
+END
+CASE(1)
+	int n = 5; 
+	int m = 7; 
+	int u_[] = {1, 1, 1, 2, 2, 3, 3};
+	  vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 
+	int v_[] = {5, 3, 2, 5, 3, 5, 4};
+	  vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 
+	int l_[] = {1, 8, 2, 3, 4, 6, 9};
+	  vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 
+	int _ = 28; 
+END
+CASE(2)
+	int n = 7; 
+	int m = 6; 
+	int u_[] = {1, 1, 2, 2, 3, 3};
+	  vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 
+	int v_[] = {2, 3, 4, 5, 6, 7};
+	  vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 
+	int l_[] = {7, 11, 6, 9, 20, 15};
+	  vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 
+	int _ = 64; 
+END
+CASE(3)
+	int n = 8; 
+	int m = 11; 
+	int u_[] = {1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 7};
+	  vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 
+	int v_[] = {2, 8, 3, 5, 4, 6, 7, 5, 6, 8, 8};
+	  vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 
+	int l_[] = {2, 3, 1, 6, 11, 8, 9, 10, 7, 4, 5};
+	  vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 
+	int _ = 12; 
+END
+CASE(4)
+	int n = 13; 
+	int m = 56; 
+	int u_[] = {1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12};
+	  vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 
+	int v_[] = {3, 4, 5, 7, 9, 12, 13, 3, 5, 8, 9, 10, 12, 13, 5, 6, 8, 9, 10, 11, 12, 5, 6, 7, 9, 11, 13, 7, 8, 9, 11, 12, 7, 8, 9, 10, 13, 8, 9, 10, 11, 12, 13, 9, 11, 12, 10, 11, 12, 13, 11, 12, 13, 12, 13, 13};
+	  vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 
+	int l_[] = {82, 240, 395, 1041, 1165, 1274, 1540, 1650, 1904, 2306, 2508, 3162, 3380, 3637, 3778, 3913, 3971, 4101, 4148, 4218, 4394, 4434, 5107, 6147, 6280, 6337, 6461, 6490, 7056, 8024, 8373, 8924, 8961, 9058, 9304, 9359, 10899, 11049, 11090, 11174, 11269, 11356, 11547, 11808, 12566, 12591, 13322, 13447, 13667, 13672, 15013, 15319, 16153, 16447, 16454, 16470};
+	  vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 
+	int _ = 504663883; 
+END
+/*
+CASE(5)
+	int n = ; 
+	int m = ; 
+	int u_[] = ;
+	  vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 
+	int v_[] = ;
+	  vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 
+	int l_[] = ;
+	  vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 
+	int _ = ; 
+END
+CASE(6)
+	int n = ; 
+	int m = ; 
+	int u_[] = ;
+	  vector <int> u(u_, u_+sizeof(u_)/sizeof(*u_)); 
+	int v_[] = ;
+	  vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_)); 
+	int l_[] = ;
+	  vector <int> l(l_, l_+sizeof(l_)/sizeof(*l_)); 
+	int _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/790-U/1B.cpp
Index: SRM/790-U/1B.cpp
==================================================================
--- SRM/790-U/1B.cpp
+++ SRM/790-U/1B.cpp
@@ -0,0 +1,201 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <tuple>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class ProposalOptimization { public:
+	double bestPath(int R, int C, int K, vector <int> roses, vector <int> tulips, vector <int> costs)
+	{
+		int S = (R - 1) + (C - 1);
+
+		vector<vector<tuple<LL, LL, LL>>> cand1(R*C), cand2(R*C);
+		dfs1(R, C, K, roses, tulips, costs, 0, 0, S/2, 0LL, 0LL, 0LL, cand1);
+		dfs2(R, C, K, roses, tulips, costs, R-1, C-1, S-S/2, 0LL, 0LL, 0LL, cand2);
+
+		double best = -1;
+		for (int i = 0; i < cand1.size(); ++i)
+			if (!cand1[i].empty() && !cand2[i].empty())
+				best = max(best, calc_best(cand1[i], cand2[i], K));
+		return best;
+	}
+
+	double calc_best(
+		vector<tuple<LL, LL, LL>> c1,
+		vector<tuple<LL, LL, LL>> c2,
+		int K
+	) {
+		sort(c1.begin(), c1.end(), [&](const tuple<LL, LL, LL>& a, const tuple<LL, LL, LL>& b) {
+			return double(get<0>(a)) / get<1>(a) > double(get<0>(b)) / get<1>(b);
+		});
+		sort(c2.begin(), c2.end(), [&](const tuple<LL, LL, LL>& a, const tuple<LL, LL, LL>& b) {
+			return double(get<0>(a)) / get<1>(a) > double(get<0>(b)) / get<1>(b);
+		});
+		double best = -1;
+		for (auto&& e1 : c1) {
+			LL r1, t1, co1; tie(r1, t1, co1) = e1;
+			double rat1 = double(r1) / t1;
+			for (auto&& e2 : c2) {
+				LL r2, t2, co2; tie(r2, t2, co2) = e2;
+				double rat2 = double(r2) / t2;
+				if (co1 + co2 <= K) {
+					best = max(best, double(r1 + r2) / (t1 + t2));
+				}
+				if (rat1 <= best && rat2 <= best)
+					break;
+			}
+		}
+		return best;
+	}
+
+	void dfs1(int R, int C, int K, const vector<int> &roses, const vector<int>& tulips, const vector<int>& costs,
+		int y, int x, int s, LL rr, LL tt, LL cc, vector<vector<tuple<LL, LL, LL>>>& cand) {
+		if (s == 0) {
+			cand[y*C+x].emplace_back(rr, tt, cc);
+			return;
+		}
+		s--;
+		rr += roses[y*C + x];
+		tt += tulips[y*C + x];
+		cc += costs[y*C + x];
+		if (y + 1 < R)
+			dfs1(R, C, K, roses, tulips, costs, y+1, x, s, rr, tt, cc, cand);
+		if (x + 1 < C)
+			dfs1(R, C, K, roses, tulips, costs, y, x+1, s, rr, tt, cc, cand);
+	}
+	void dfs2(int R, int C, int K, const vector<int> &roses, const vector<int>& tulips, const vector<int>& costs,
+		int y, int x, int s, LL rr, LL tt, LL cc, vector<vector<tuple<LL, LL, LL>>>& cand) {
+		rr += roses[y*C + x];
+		tt += tulips[y*C + x];
+		cc += costs[y*C + x];
+		if (s == 0) {
+			cand[y*C+x].emplace_back(rr, tt, cc);
+			return;
+		}
+		s--;
+		if (y - 1 >= 0)
+			dfs2(R, C, K, roses, tulips, costs, y - 1, x, s, rr, tt, cc, cand);
+		if (x - 1 >= 0)
+			dfs2(R, C, K, roses, tulips, costs, y, x - 1, s, rr, tt, cc, cand);
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const double& Expected, const double& Received) {
+ bool ok = (abs(Expected - Received) < 1e-9);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, ProposalOptimization().bestPath(R, C, K, roses, tulips, costs));}
+int main(){
+
+CASE(0)
+	int R = 2; 
+	int C = 2; 
+	int K = 100; 
+	int roses_[] = {0, 2, 3, 0};
+	  vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 
+	int tulips_[] = {0, 3, 5, 0};
+	  vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 
+	int costs_[] = {0, 70, 80, 0};
+	  vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
+	double _ = 0.6666666666666667; 
+END
+CASE(1)
+	int R = 2; 
+	int C = 2; 
+	int K = 100; 
+	int roses_[] = {0, 2, 3, 0};
+	  vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 
+	int tulips_[] = {0, 3, 5, 0};
+	  vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 
+	int costs_[] = {0, 170, 100, 0};
+	  vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
+	double _ = 0.6; 
+END
+CASE(2)
+	int R = 3; 
+	int C = 3; 
+	int K = 98; 
+	int roses_[] = {0, 1, 1, 1, 1, 1, 1, 1, 0};
+	  vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 
+	int tulips_[] = {0, 1, 1, 1, 1, 1, 1, 1, 0};
+	  vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 
+	int costs_[] = {0, 33, 33, 33, 33, 33, 33, 33, 0};
+	  vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
+	double _ = -1.0; 
+END
+CASE(3)
+	int R = 5; 
+	int C = 9; 
+	int K = 622; 
+	int roses_[] = {0, 2, 12, 1, 6, 10, 10, 24, 3, 1, 7, 4, 4, 1, 37, 4, 6, 8, 2, 20, 5, 20, 6, 7, 22, 3, 2, 8, 31, 18, 5, 28, 11, 1, 34, 1, 4, 2, 6, 1, 6, 9, 5, 7, 0};
+	  vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 
+	int tulips_[] = {0, 4, 37, 22, 3, 14, 10, 6, 5, 6, 5, 17, 4, 7, 12, 3, 1, 3, 3, 1, 5, 1, 11, 37, 6, 24, 6, 3, 21, 1, 2, 27, 7, 1, 8, 1, 8, 1, 26, 20, 6, 6, 6, 7, 0};
+	  vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 
+	int costs_[] = {0, 19, 70, 79, 18, 43, 49, 65, 16, 38, 61, 69, 43, 12, 62, 11, 44, 35, 7, 62, 40, 88, 60, 57, 65, 38, 46, 18, 69, 87, 28, 80, 47, 5, 64, 1, 15, 3, 86, 41, 86, 21, 56, 28, 0};
+	  vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
+	double _ = 2.161290322580645; 
+END
+CASE(4)
+	int R = 2; 
+	int C = 3; 
+	int K = 15; 
+	int roses_[] = {0, 1, 3, 1, 1, 0};
+	  vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 
+	int tulips_[] = {0, 1, 2, 6, 1, 0};
+	  vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 
+	int costs_[] = {0, 1, 18, 9, 1, 0};
+	  vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
+	double _ = 1.0; 
+END
+CASE(5)
+	int R = 17; 
+	int C = 17; 
+	int K = 1000000000; 
+	int roses_[] = { 0,17713,98005,85972,85419,41343,40594,75347,93890,14460,88192,13259,57509,23864,11665,83891,86272,15177,6741,719,45954,28976,17494,69645,85635,41641,83750,72134,25460,59238,79843,19241,42910,82037,76014,94424,87835,60518,81389,71620,22925,99806,96380,13812,53986,64087,72645,71066,59167,81512,79112,79376,94122,68917,6461,20829,58265,20191,49403,72161,75464,63255,68477,94619,60731,90043,25099,9348,78594,23510,42035,21938,33854,25015,56547,55185,92344,41515,90935,19182,66704,83072,21731,64543,17498,5861,13274,10448,80628,36311,10855,57786,99593,82225,36546,63772,74592,3376,16070,89074,46067,27551,2731,66618,89683,62388,9681,48186,61936,80333,21392,27448,15920,92274,51645,40695,32491,39887,41545,90544,85138,57454,91032,69274,60520,68444,22949,54533,19920,96297,93530,71936,23721,16630,97250,26918,4078,31547,22942,98473,21503,96772,55133,79486,13707,14208,42654,61512,38364,6095,13808,11189,64709,1277,99824,76973,48998,19603,12891,7593,89029,66987,44448,83779,85479,16134,23980,33936,85444,98235,21115,41423,58343,86809,12650,80022,11253,96942,2552,63303,61702,93988,12874,19507,47539,10623,80913,93724,6698,78407,84626,19955,94554,18908,17534,7815,49133,86196,14223,59940,49525,52174,83198,81931,90518,73849,48514,1486,64897,16791,73509,83061,41101,24339,40911,52042,41565,12010,16810,91464,72979,42196,21127,75435,19330,42120,12526,24400,35862,46552,68157,65335,75713,17243,95124,96114,15670,25945,29786,68448,18314,92647,57702,87304,15779,38562,33340,40193,39768,37511,65405,37272,43597,16314,57010,37359,11549,53388,39583,49716,95725,15464,20113,10362,9822,88209,44604,54927,20688,17684,13526,36081,30399,35955,10775,80362,56735,69285,87764,8086,96866,64919,41125,50869,39730,85021,23265,7472,0 };
+	  vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 
+	int tulips_[] = { 0,9769,3028,85209,31522,29537,15670,9872,74152,90511,30552,85947,48407,63109,8661,78971,98650,11447,16597,52768,57998,62459,97353,46290,99556,65315,29642,65209,5186,6575,13996,78253,85369,27644,20307,85963,42024,7704,13495,97337,23681,6532,51458,63148,74251,17312,94640,37763,51284,93920,20807,52788,54022,73863,26384,57486,95723,63913,4796,7952,10401,57086,94030,60544,83498,3953,33518,64072,50391,65430,22260,97536,8499,95372,56623,15411,40845,31869,22748,40259,11731,34988,5007,16729,10429,7649,25527,57598,90154,52284,32678,51334,23627,28031,24523,17301,28375,56446,24804,97224,7073,42305,36863,58364,89465,22514,64934,51833,69432,15144,4114,19130,58231,56947,10697,89774,27353,4582,98877,16611,4898,36227,69319,10145,8021,91236,78226,68164,24304,38902,99049,55563,15667,89339,53542,55528,56648,83841,34369,83507,10322,54066,2109,38691,54068,4146,34578,10539,39825,53008,38115,76977,82128,36250,79640,62876,60224,82458,20672,74027,13015,17336,40022,9466,16190,95201,1984,71439,31622,86304,21238,77681,42793,58347,64545,8461,61198,61462,17351,11199,76388,88024,7151,64715,43508,86176,16988,12823,60358,65930,19270,93090,76541,35446,81321,33736,78439,55714,15090,40355,26655,49819,94411,44956,87498,42104,16999,70319,25812,44599,52167,68978,67435,19497,57032,15935,12790,87411,12311,28746,24555,72121,86503,11097,82830,32400,67871,33171,31720,2775,31814,29149,48084,47054,29581,58158,16032,53299,55162,42943,93528,34878,86465,34271,17400,3307,35604,20670,87995,92288,10165,7459,76834,64926,66418,15671,55829,76154,59843,15184,83445,28295,94417,56173,60185,44153,35721,15819,23521,61573,46060,73816,47811,98808,2077,98142,64358,16098,70327,52811,84917,81751,65018,81568,30895,98370,73153,60908,0 };
+	  vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 
+	int costs_[] = { 0,66626,71469,70328,62092,18516,71453,8941,94840,56510,68091,96708,89072,20847,3714,71081,89790,28668,86537,10174,42756,15676,79596,90914,50966,20774,60749,64722,47682,83245,71339,62762,86168,4467,37556,64067,86974,68222,67580,43199,84847,96631,97379,92419,97088,72353,66088,65870,6299,80307,58086,51789,26660,70308,64938,58409,89127,31537,70188,35122,46821,45966,19772,40138,32629,5610,64958,64710,77776,50851,38811,72706,37105,65281,67607,99603,4055,37124,26717,10987,76334,88961,31961,69553,95339,3225,73746,16227,84040,95606,88934,14394,6224,20213,15690,9967,97156,27312,14112,45814,93837,74937,14588,23671,37173,99909,90322,8992,41632,80695,20971,35245,85613,35347,45680,86559,70987,51767,47354,90383,5099,55635,56545,97614,28933,67589,23677,69586,86774,70573,39509,77282,89564,7817,56970,49503,49734,48415,69528,9866,52165,40974,60469,75270,5606,4070,86249,30553,43234,97015,99573,23569,15832,66396,12179,21426,92167,56115,46838,59105,45361,54968,35141,59292,2262,10035,76893,20331,35900,22459,64940,97162,67481,23505,34746,85004,1951,34258,43323,28625,74448,56702,65510,50921,6365,15538,41141,78509,60953,79442,73331,90601,21192,94533,37991,17125,39320,72663,27302,97902,96791,88361,97223,29252,44615,20549,42367,85876,47270,68176,2764,51818,76763,33526,23387,47643,23350,28166,76490,80377,22181,6301,75316,65836,89813,20908,94777,28441,58911,27900,36109,70611,42438,91477,64770,17579,44088,47482,60394,59538,20487,70009,42539,91762,77637,75959,90292,45316,50083,31783,63713,340,30832,21662,13752,84525,96226,40981,37339,6681,69898,43800,42643,45928,41106,42960,23017,89656,82740,38315,66917,64709,85928,66375,50321,41659,91826,81211,63149,73364,18299,50835,27382,7050,56552,46876,34589,20853,0 };
+	  vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
+	  double _ = -2;
+END
+/*
+CASE(6)
+	int R = 5; 
+	int C = 60; 
+	int K = 100000000; 
+	int roses_[] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
+	  vector <int> roses(roses_, roses_+sizeof(roses_)/sizeof(*roses_)); 
+	int tulips_[] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
+	  vector <int> tulips(tulips_, tulips_+sizeof(tulips_)/sizeof(*tulips_)); 
+	int costs_[] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };
+	  vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 
+	double _ = -2; 
+END
+*/
+}
+// END CUT HERE