편의점의 작은 추천대

문제

한 편의점은 계산대 옆에 작은 추천대를 설치하려 한다. 창고에는 추천대에 올릴 수 있는 상품이 N개 있으며, 각 상품에는 입고 목록에 적힌 순서대로 1번부터 N번까지 번호가 붙어 있다. 같은 종류의 상품이 여러 개 있어도 입고 목록의 항목이 다르면 서로 다른 상품으로 취급한다. 추천대에는 정확히 K개의 상품을 놓을 수 있고, 각 상품은 최대 한 번만 선택할 수 있다. 점장은 손님이 부담 없이 살 수 있는 상품을 먼저 소개하려 한다. 이를 위해 모든 상품의 우선순위를 다음과 같이 정했다. 가격이 더 낮은 상품의 우선순위가 높다. 가격이 같다면 판매 가능 기간이 더 짧게 남은 상품의 우선순위가 높다. 가격과 남은 판매 가능 기간이 모두 같다면 상품 번호가 더 작은 상품의 우선순위가 높다. 남은 판매 가능 기간은 오늘을 포함하여 상품을 판매할 수 있는 날짜의 수이며, 모든 상품은 오늘 판매할 수 있다. 직원은 이 우선순위에 따라 상품을 한 줄로 세운 뒤 맨 앞에서부터 K개를 추천대에 옮긴다. 선택 과정에서 예산 제한이나 상품 종류에 관한 추가 조건은 적용하지 않는다. 판매 가능 기간은 상품을 고르는 우선순위에만 사용하며, 가격을 할인하거나 상품을 제외하는 기준으로 사용하지 않는다. 상품을 옮기는 동안 날짜가 바뀌는 일도 없다. 점장은 추천대에 놓인 상품을 한 개씩 모두 구매할 때의 가격 합계와, 직원이 상품을 옮기는 순서를 기록하려 한다. 선택된 상품의 가격을 모두 더한 값과 선택된 상품 번호를 우선순위가 높은 순서대로 구한다. 상품 번호는 입력에 등장한 순서로 정해지므로 상품을 정렬한 뒤에도 원래 번호를 사용해야 한다.

입력

첫째 줄에 상품의 수 N과 추천대에 놓을 상품의 수 K가 공백으로 구분되어 주어진다.
다음 N개의 줄 중 i번째 줄에는 i번 상품의 가격 P_i와 남은 판매 가능 기간 D_i가 공백으로 구분되어 주어진다.
모든 입력값은 정수이며 1 ≤ K ≤ N ≤ 100,000, 1 ≤ P_i ≤ 1,000,000, 1 ≤ D_i ≤ 365이다.

출력

첫째 줄에 선택된 K개 상품의 가격 합계를 출력한다. 둘째 줄에 선택된 상품 번호 K개를 우선순위가 높은 순서대로 공백으로 구분하여 출력한다.

6 4
7 3
4 8
4 2
7 1
4 2
9 1

19
3 5 2 4

4 4
3 2
3 2
1 9
3 1

10
3 4 1 2

1 1
1000000 365

1000000
1

출처: Devin.KR 자체 제작