별 모으기
면접 대비시간 제한2초메모리 제한512 MB
별 n개의 소요 시간과 해금 조건이 주어집니다. 조건을 만족하는 순서로 k개를 골라 총 소요 시간을 최소로 구합니다.
문제
당신은 최신 Super Mario 게임을 최대한 빨리 클리어하려고 한다. 이 게임에는 모을 수 있는 별이 n개 있고, 목표는 그중 아무거나 k개를 모으는 것이다. 별마다 얻는 데 걸리는 시간이 정해져 있다. 별을 하나 모으고 나면 Mario는 게임의 시작 지점에 다시 나타나므로, 어떤 별들을 어떤 순서로 모으든 걸리는 시간은 같다. 다만 일부 별은 이미 모은 별의 개수가 특정 수 이상이 되어야 모을 수 있다.
별에 대한 정보가 주어질 때, 별 k개를 모을 수 있는 최소 시간을 구하거나, 모을 수 없다면 불가능함을 판별하라.
입력
첫째 줄에 별의 개수 n (1 ≤ n ≤ 200 000)과 모아야 하는 별의 개수 k (1 ≤ k ≤ n)가 주어진다.
다음 n개의 줄에 별의 정보가 주어진다. 각 줄에는 그 별을 모으는 데 걸리는 시간 t (1 ≤ t ≤ 10^9)와 그 별을 모을 수 있게 되기 전에 모아야 하는 별의 개수 d (0 ≤ d < n)가 주어진다.
출력
별 k개를 모으는 최소 시간을 출력한다. 별 k개를 모을 수 없다면 IMPOSSIBLE을 출력한다.