헌책방

상근이가 사는 도시에는 헌책방이 있다. 데이트 비용을 감당하기 어려워진 상근이는 집에 있는 책을 헌책방에 팔기로 했다. 각 책에는 기준 가격이 정해져 있고, 헌책방은 기본적으로 이 가격으로 책을 매입한다.

헌책방은 모든 책을 소설, 만화, 잡지 등 10개의 장르로 분류하며, 장르에는 1번부터 10번까지 번호가 매겨져 있다. 이 가게는 같은 장르의 책을 한 번에 여러 권 매입할 때 더 높은 값을 쳐 준다.

같은 장르의 책을 한 번에 $T$권 매입하면, 그 $T$권 각각의 매입 가격이 기준 가격보다 $T-1$원씩 높아진다. 예를 들어 같은 장르에서 기준 가격이 각각 $100$원, $120$원, $150$원인 책 세 권을 한 번에 팔면, 세 권을 함께 매입하므로 각 매입 가격은 $102$원, $122$원, $152$원이 된다.

상근이는 내일 데이트를 위해 가지고 있는 책 $N$권 중 정확히 $K$권을 팔려고 한다. 각 책의 기준 가격과 장르 번호가 주어질 때, 팔 $K$권을 잘 골라 얻을 수 있는 총 매입 가격의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 상근이가 가진 책의 수 $N$과 팔려고 하는 책의 수 $K$가 주어진다. ($2 \le N \le 2000$, $1 \le K < N$)

다음 $N$개의 줄에 각 책의 기준 가격 $C_i$와 장르 번호 $G_i$가 공백으로 구분되어 주어진다. ($1 \le C_i \le 10^5$, $1 \le G_i \le 10$)

정확히 $K$권을 팔 때 얻을 수 있는 총 매입 가격의 최댓값을 첫째 줄에 출력한다.

각 장르에서 파는 책 수 $t$가 정해지면 추가 금액 $t(t-1)$은 항상 같으므로, 그 장르에서는 기준 가격이 높은 순으로 $t$권을 고르는 것이 언제나 유리하다. 따라서 장르마다 몇 권을 팔지만 결정하면 되고, 10개 장르에서 파는 권수의 합이 정확히 $K$가 되도록 배낭 문제처럼 조합해 최댓값을 찾으면 된다.