#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
using integer = int;
#define int long long
struct DS
{
int n;
vector<pair<int, int>> a;
void init(int N, vector<pair<int, int>> A)
{
a = A;
n = N;
}
int query_kth(int l, int r, int k)
{
vector<int> rs;
for (auto it : a)
{
if (it.first >= l and it.first <= r)
rs.push_back(it.second);
}
if (rs.size() < k)
return n + 1;
sort(rs.begin(), rs.end());
return rs[k - 1];
}
int cate_incl(int l, int r)
{
int ct = 0;
for (auto it : a)
{
if (it.first >= l and it.second <= r)
ct++;
}
return ct;
}
};
DS wavelet;///eu cand nu dau overkill
int n;
void init(integer N, integer A[], integer B[])
{
n = N;
vector<pair<int, int>> a;
for (int i = 0; i < N; i++)
a.push_back({A[i], B[i]});
wavelet.init(n, a);
}
integer can(integer M, integer K[])
{
int m = M, sm = 0;
map<int, int> mp;
for (int i = 0; i < m; i++)
{
mp[K[i]] += K[i], sm += K[i];
}
if (sm > n)
return 0;
vector<pair<int, int>> a;
for (auto it : mp)
a.push_back(it);
a.push_back({0, 0});
sort(a.begin(), a.end());///probabil era deja sortat dar idk
set<int> s;
vector<int> dp(a.size());
dp[0] = 0;
s.insert(0);
set<pair<int, int>> bang;
int ans = wavelet.cate_incl(1, n);
for (int i = 1; i < a.size(); i++)
{
while (!bang.empty())
{
pair<int, int> it = *bang.begin();
if (it.first >= a[i].first)
break;
bang.erase(it);
int xx = *s.upper_bound(it.second);
int zz = it.second;
s.erase(xx);
if (s.upper_bound(it.second) != s.end())
{
int yy = *s.upper_bound(it.second);
bang.erase({wavelet.query_kth(a[xx].first + 1, a[yy].first - 1, dp[yy] - dp[xx]), xx});
bang.insert({wavelet.query_kth(a[zz].first + 1, a[yy].first - 1, dp[yy] - dp[zz]), zz});
}
}
int cn = *s.rbegin();
dp[i] = a[i].second + dp[cn] + wavelet.cate_incl(a[cn].first + 1, a[i].first - 1);
bang.insert({wavelet.query_kth(a[cn].first + 1, a[i].first - 1, dp[i] - dp[cn]), cn});
/*for (int j = 0; j < i; j++)
dp[i] = max(dp[i], dp[j] + a[i].second + wavelet.cate_incl(a[j].first + 1, a[i].first - 1));*/
ans = max(ans, dp[i] + wavelet.cate_incl(a[i].first + 1, n));
}
if (ans > n)
return 0;
else
return 1;
}
