The Used Bookstore

There is a used bookstore in the city where Sanggeun lives. Struggling to keep up with the cost of his dates, Sanggeun decides to sell some of the books he owns to the bookstore. Every book has a fixed base price, and by default the bookstore buys it at that price.

The bookstore sorts all books into 10 genres, such as novels, comics, and magazines, numbered from 1 to 10. When the store buys several books of the same genre together, it pays more for them.

If $T$ books of the same genre are bought together, each of those $T$ books is purchased for $T-1$ won more than its base price. For example, if three same-genre books with base prices $100$, $120$, and $150$ won are sold together, they are bought for $102$, $122$, and $152$ won respectively, because all three are purchased at once.

For tomorrow's date, Sanggeun wants to sell exactly $K$ of the $N$ books he owns. Given the base price and genre of each book, write a program that finds the maximum total purchase price he can obtain by choosing which $K$ books to sell.

The first line contains the number of books $N$ that Sanggeun owns and the number of books $K$ he wants to sell. ($2 \le N \le 2000$, $1 \le K < N$)

Each of the next $N$ lines contains the base price $C_i$ and genre $G_i$ of a book, separated by a space. ($1 \le C_i \le 10^5$, $1 \le G_i \le 10$)

Print, on the first line, the maximum total purchase price obtainable by selling exactly $K$ books.

Once you fix how many books $t$ you sell from a genre, the added amount $t(t-1)$ is the same, so within that genre it is always best to take the $t$ highest-priced books. You therefore only need to decide how many books to sell from each genre, and combine the 10 genres like a knapsack so that the total number sold is exactly $K$.