#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair P; int dp[5050][5050]; int main() { int n, c; cin>>n>>c; int p[5050]; for(int i=0; i>p[i]; } sort(p, p+n, greater()); vector v1, v2; for(int i=0; i>t>>x; if(t==1) v1.push_back(x); else v2.push_back(x); } sort(v1.begin(), v1.end(), greater()); sort(v2.begin(), v2.end(), greater()); const int INF=1e9+7; for(int i=0; i<=n; i++){ for(int j=0; j<=v1.size(); j++){ dp[i][j]=INF; } } dp[0][0]=0; for(int i=0; i