#include "bits/stdc++.h" #include #define rep(i,n) for(int i = 0; i < n; i++) typedef long long ll; typedef unsigned long long ull; using namespace std; #define vll vector> #define vl vector #define vi vector #define vii vector> #define pb push_back #define pf push_front #define ld long double #define Sort(a) sort(a.begin(),a.end()) #define cSort(a,cmp) sort(a.begin(),a.end(),cmp) #define reSort(a) sort(a.rbegin(), a.rend()) static const ll llMAX = numeric_limits::max(); static const int intMAX = numeric_limits::max(); static const ll llMIN = numeric_limits::min(); static const int intMIN = numeric_limits::min(); static const ll d_5 = 100000; static const ll d9_7 = 1000000007; static const ll d_9 = 1000000000; static const double PI=3.14159265358979323846; template T gcd(T a,T b){ if(a==0){ return b; }else if(b==0){ return a; } while(1) { if(a < b) swap(a, b); if(!b) break; a %= b; } return a; } ll digitpower(ll a,ll b){//aのb乗を計算 if(b==1){ return a; }else if(b==0){ return 1; } int mode=0; if(mode==0){ if(b%2==1){ ll tmp = digitpower(a,(b-1)/2); tmp%=d9_7; tmp*=tmp; tmp%=d9_7; tmp*=a; return (tmp)%d9_7; }else{ ll tmp = digitpower(a,(b)/2); tmp%=d9_7; tmp*=tmp; tmp%=d9_7; return (tmp)%d9_7; } }else{ if(b%2==1){ ll tmp = digitpower(a,(b-1)/2); tmp*=tmp; tmp*=a; return (tmp); }else{ ll tmp = digitpower(a,(b)/2); tmp*=tmp; return (tmp); } } return 0; } template void Printvector(std::vector &a){ int size = a.size(); rep(i,size){ cout< void Printvector(std::vector> &a){ int size = a.size(); rep(i,size){ int size2=a[i].size(); rep(j,size2){ cout< primes(ll n){ unordered_set ret; for(ll i=2;i*i<=n;i++){ if(n%i==0){ ret.insert(i); ret.insert(n/i); } } return ret; } long long modinv(long long a, long long m) {//modの逆元 long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } vl facs(1000008,-1); ll Factrial(ll num){ if(facs[num]!=-1){ return facs[num]; } if(num==1||num<=0){ return 1; }else if(num<0){ printf("ERROR_minus\n"); return 0; }else{ facs[num]=(num*Factrial(num-1))%d9_7; return facs[num]; } } vl invs(2000010,-1); ll linercomb(ll n,ll k, ll mod){//n,kの線形時間で求める if(n>n; vl a(n+1); vl b(n+1); vl d(n); rep(i,n+1){ cin>>a[i]; } rep(i,n+1){ cin>>b[i]; } rep(i,n){ cin>>d[i]; } Sort(d); int lk=0,rk=n; while(lk!=rk){ int nowk=(lk+rk+1)/2; vector> dp(nowk+1,vector(nowk+1,false)); vl d2(nowk); rep(i,nowk){ d2[i]=d[nowk-1-i]; } dp[0][0]=true; rep(i,nowk+1){ rep(j,nowk+1){ if(i+j>=nowk)break; if(i=d2[i+j+1 -1] && dp[i][j]){ dp[i+1][j]=true;; } } if(j=d2[i+j+1 -1] && dp[i][j]){ dp[i][j+1]=true; } } } } bool tmp=false; for(int i=0;i<=nowk;i++){ if(dp[i][nowk-i]){ tmp=true; } } if(tmp){ lk=nowk; }else{ rk=nowk-1; } } cout<