헌책방

상근이가 살고있는 도시에는 헌책방이 있다. 데이트 비용을 점점 감당할 수 없게된 상근이는 집에 있는 책을 헌책방에 팔려고 한다. 각 책에는 기준 가격이 정해져있고, 헌책방은 이 가격으로 매입한다.

헌책방은 책을 소설, 만화, 잡지등 10개의 장르로 분류한다. 장르는 1부터 10까지 번호가 매겨져 있다. 이 가게는 같은 장르의 책을 한 번에 매입할 때, 고가로 매입해 준다.

같은 장르의 책을 T권 매입할 때, 책 한 권 당 매입 가격이 기준 가격보다 T-1원 높아진다. 예를 들어, 같은 장르에서 기준 가격이 100원, 120원, 150원인 책을 한 번에 헌책방에 판다면, 매입 가격은 102원, 122원, 152원이 된다.

상근이는 내일 데이트를 가기 위해서 가지고 있는 책 N권 중 K권을 팔려고 한다.

책 N권의 기준 가격과 장르 번호가 주어졌을 때, 총 매입 가격의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 상근이가 가지고 있는 책의 개수 N과 파려고 하는 책의 수 K가 주어진다. (2 ≤ N ≤ 2000, 1 ≤ K < N)

둘째 줄부터 N개 줄에는 상근이가 가지고 있는 책의 기준 가격 Ci와 장르 Gi가 공백으로 구분되어 주어진다. (1 ≤ Ci ≤ 105, 1 ≤ Gi ≤ 10)

첫째 줄에 총 매입 가격의 최댓값을 출력한다.

2, 4, 6, 7번 책을 판매하면 된다.