#include<iostream>
using namespace std;
 
int n , k, a , b;
long long dp[51][51];
 
long long  calc(int cur, int made)
{
    if( made > k )
        return 0;

#include<iostream>
using namespace std;
 
#define PIE (double)3.1415926535897932384626
#define eps 1e-7
double pies[10001];
int n, f, temp;
inline bool ok(double mid)
{
    int total = 0;

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<deque>
#include<queue>

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<deque>
#include<queue>

#include<iostream>
using namespace std;
 
int n , L, C;
int dp[1001][501];
int topics[1001];
int needed;
 
#define oo (int)1e9
 

#include<iostream>
using namespace std;
 
const int oo (1e9);
 
int memo[10001];
int coins[501][2];
int n;
 
int dp(int mon)

#include<iostream>
using namespace std;
 
const int oo (1e9);
int budget, n;
 
int parties[101][2];
int memo[101][501];
int dp(int indx, int mon)
{

#include<iostream>
using namespace std;
#include<vector>
#include<queue>
#include<cstring>
 
const int oo (1e9);
int M, N;
 
inline bool ok(int  y, int x)

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<algorithm>
#include<string>
#include<cstring>

#include<iostream>
using namespace std;
 
const int oo (1e9);
 
int n;
int cards[1001];
int dp[1001][1001];
int calc(int l , int r)
{

#include<queue>
#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<algorithm>
#include<string>
#include<sstream>

#include<iostream>
#include <string>
#include <vector>
#include<set>
#include<queue>
#include<map>
#include<cmath>
#include<sstream>
#include<cstdio>
#include<algorithm>

#include<iostream>
#include<algorithm>
using namespace std;
#include<cstring>
#include<vector>
 
 
vector<vector<int> > list;
vector<vector<int> > transpose;
vector<vector<int> > components;

#include<iostream>
using namespace std;
#include<queue>
#include<cstring>
 
char grid[111][111];
 
int r , c, moves[][2] = { {0,1},{1,0},{0,-1},{-1,0} };
 

#include<iostream>
using namespace std;
#include<queue>
#include<set>
#include<map>
#include<string>
 
int dp[1001];
 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
using namespace std;
#include<set>
 
vector<string> current;
set<string> Insignificants;

#include "assert.h"
#include "ctype.h"
#include "math.h"
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "time.h"
#include "algorithm"
#include "numeric"
#include "functional"

 
#include<iostream>
using namespace std;
#include<algorithm>
int N, C;
int stalls[100000];
const int INF = 2000000000;
inline bool ok(int diff) {