C++ :

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 30000
#define MAX_M 60000
using namespace std;
int n;
int m;
struct Fish
{
    int w;
    int v;
    inline bool operator<(const Fish&x)const
    {
        if(w!=x.w) return w<x.w;
        return v>x.v;
    }
};
Fish a[MAX_N + 5];
int ans;

int main()
{
    scanf("%d%d", &n, &m);
    int mid = 0;
    for(register int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &a[i].w, &a[i].v);
        if(a[i].w & 1) ++mid;
    }
    sort(a + 1, a + n + 1);
    for(register int i = 1; i <= n; ++i)
    {
        a[i].v += a[i - 1].v;
    }
    m = min(m, mid + (n - mid << 1));
    for(register int i = 0; i <= m; i += 2)
    {
        if((m-i)<=mid&&mid+(i>>1)<=n)
        {
            ans=max(ans, a[m - i].v + a[mid + (i >> 1)].v - a[mid].v);
        }
    }
    printf("%d", ans);
    return 0;
}