34936번 - 블록 생성

문제

서울사이버대학교 빅데이터·정보보호학과 노교수는 테스트 블록체인을 운영하고 있다. 이 블록체인의 트랜잭션 및 블록 생성 규칙은 다음과 같다.

• 각 트랜잭션을 생성 시간과 수수료로 나타낼 수 있으며, 생성 직후 트랜잭션 풀에 넣는다.
• 생성 시간이 현재로부터 일정 범위 이내인 트랜잭션들 중, 수수료가 큰 트랜잭션부터 $K$개를 트랜잭션 풀에서 꺼낸 뒤 블록을 생성한다. 블록 생성자는 블록에 속한 트랜잭션들의 수수료 합을 얻게 된다.
• 수수료가 같다면 먼저 생성된 트랜잭션을 선택하며, 트랜잭션 풀에 선택 가능한 트랜잭션의 수가 $K$개 미만이면 모두 선택한다.

노교수는 AI융합기술학과 석사 및 박사 과정 등록금을 지원 자격으로, 이 규칙에 따라 블록을 생성했을 때 얻는 수수료의 총합을 계산하도록 했다. 대학원 진학을 희망하는 뚜루는 이 문제를 풀기 위해 여러분에게 도움을 요청하였다. 뚜루를 도와주자.

입력

첫 번째 줄에 사건의 수 $N,ドル 유효 시간 $T,ドル 그리고 한 블록에 선택할 수 있는 트랜잭션의 최대 개수 $K$가 주어진다. (1ドル \le N \le 200,000円; 0 \le T \le 10^9; 1 \le K \le N$) 두 번째 줄부터 $N$개의 줄에 걸쳐 시간이 감소하지 않는 순서대로 사건이 주어진다. 각 사건은 아래의 두 유형 중 하나이다. (0ドル \le t, f \le 10^9$)

• 1 t f: 시간 $t$에 수수료가 $f$인 트랜잭션이 생성되어 트랜잭션 풀에 저장된다.
• 2 t: $t$를 기준으로 생성 시간이 $T$ 이하로 차이나는 트랜잭션 중에서 위의 방식대로 선택하여 블록으로 생성한다.

사건은 모두 입력에서 주어진 순서대로 처리하며, 동일한 시간에 여러 개의 사건이 주어질 수 있다.

입력으로 주어지는 수는 모두 정수이다.

출력

모든 사건을 순서대로 처리했을 때 트랜잭션의 수수료 총합을 출력하자.

제한

노트