시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 307 | 158 | 136 | 55.967% |
상근이가 살고있는 도시에는 헌책방이 있다. 데이트 비용을 점점 감당할 수 없게된 상근이는 집에 있는 책을 헌책방에 팔려고 한다. 각 책에는 기준 가격이 정해져있고, 헌책방은 이 가격으로 매입한다.
헌책방은 책을 소설, 만화, 잡지등 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)
첫째 줄에 총 매입 가격의 최댓값을 출력한다.
7 4 14 1 13 2 12 3 14 2 8 2 16 3 11 2
60
2, 4, 6, 7번 책을 판매하면 된다.
Olympiad > Japanese Olympiad in Informatics > JOI 2010/2011 2번