#include <bits/stdc++.h>                                                                  
                                                                                          
using namespace std;                                                                      
                                                                                          
int n, k;                                                                                 
int g_idx[10] = { 0 };                                                                    
int books[10][2000] = {{ 0 }};                                                            
int table[10][2001] = {{ 0 }};                                                            
int dp[10][2001];                                                                         
                                                                                          
int solve(int idx, int cnt) {                                                             
                                                                                          
    if(idx == 10) return 0;                                                               
    if(dp[idx][cnt] != -1) return dp[idx][cnt];                                           
                                                                                          
    int ret = 0;                                                                          
                                                                                          
    for(int i = 0; i <= g_idx[idx]; ++i) {                                                
        if(cnt >= i && !(i != 0 && table[idx][i] == 0)) {                                 
            ret = max(ret, solve(idx + 1, cnt - i) + table[idx][i]);                      
        }                                                                                 
    }                                                                                     
                                                                                          
    return dp[idx][cnt] = ret;                                                            
                                                                                          
}                                                                                         
                                                                                          
int main() {                                                                              
                                                                                          
    int c, g;                                                                             
                                                                                          
    cin >> n >> k;                                                                        
                                                                                          
    for(int i = 0; i < n; ++i) {                                                          
        cin >> c >> g; --g;                                                               
        books[g][g_idx[g]++] = c;                                                         
    }                                                                                     
                                                                                          
    for(int i = 0; i < 10; ++i) {                                                         
        sort(&books[i][0], &books[i][0] + g_idx[i], greater<int>());                      
    }                                                                                     
                                                                                          
    for(int i = 0; i < 10; ++i) {                                                         
        for(int j = 1; j <= g_idx[i]; ++j) {                                              
            table[i][j] = table[i][j - 1] + books[i][j - 1] + 2 * (j - 1);                
        }                                                                                 
    }                                                                                     
                                                                                          
    /*                                                                                    
    for(int i = 0; i < 2; ++i) {                                                          
        for(int j = 0; j < n; ++j) {                                                      
            cout << books[i][j] << " ";                                                   
        }                                                                                 
        cout << endl;                                                                     
    }                                                                                     
    cout << endl;                                                                         
                                                                                          
                                                                                          
    for(int i = 0; i < 10; ++i) {                                                         
        for(int j = 0; j <= g_idx[i]; ++j) {                                              
            cout << table[i][j] << " ";                                                   
        }                                                                                 
        cout << endl;                                                                     
    }                                                                                     
    cout << endl;                                                                         
    */                                                                                    
                                                                                          
    memset(dp, -1, sizeof(dp));                                                           
                                                                                          
    cout << solve(0, k) << endl;                                                          
                                                                                          
}                                                                                         

Measured memory_bytes: 1352