마감 전 세 접시

문제

카페에서는 영업을 마치기 전에 진열된 디저트 중 정확히 세 접시를 골라 마감 꾸러미를 만든다. 진열된 접시에는 1번부터 N번까지 번호가 붙어 있으며, 각 접시의 가격과 종류가 기록되어 있다. 종류는 1, 2, 3 중 하나다. 같은 종류의 디저트가 여러 접시 있을 수 있고, 가격이 같은 접시도 서로 다른 접시로 취급한다. 꾸러미에는 세 종류의 디저트가 모두 들어가야 한다. 따라서 고른 세 접시의 종류는 서로 달라야 한다. 또한 세 접시의 가격 합은 손님이 정한 예산 B를 넘을 수 없다. 예산과 정확히 같은 금액을 사용하는 것은 허용된다. 각 접시는 한 번만 고를 수 있으며, 세 접시보다 적게 고른 꾸러미는 만들 수 없다. 직원은 조건을 만족하는 꾸러미 중 가격 합이 가장 큰 것을 선택하려 한다. 가격 합이 같은 꾸러미가 여러 개라면 접시 번호를 이용해 하나를 결정한다. 각 꾸러미의 접시 번호를 작은 순서로 나열하여 (a, b, c)로 나타낸다. 먼저 a가 작은 꾸러미를 선택하고, a가 같으면 b가 작은 꾸러미를 선택하며, a와 b가 모두 같으면 c가 작은 꾸러미를 선택한다. 가격이나 종류 순서로 번호를 다시 붙이지 않는다. 예를 들어 번호가 다른 두 접시의 가격과 종류가 모두 같더라도, 어느 접시를 골랐는지에 따라 동점 처리 결과가 달라질 수 있다. 반대로 번호가 작은 접시를 포함했더라도 가격 합이 더 작다면 선택하지 않는다. 가격 합을 가장 먼저 비교한 뒤에만 번호를 비교한다. 진열 정보와 예산이 주어질 때 선택할 세 접시의 번호와 가격 합을 구한다. 어떤 종류의 접시가 없거나, 모든 가능한 세 접시의 가격 합이 예산을 넘는 등 조건에 맞는 꾸러미가 없다면 만들 수 없음을 출력한다.

입력

첫째 줄에 정수 N과 B가 공백으로 구분되어 주어진다. 3 ≤ N ≤ 100, 1 ≤ B ≤ 30000이다.
다음 N개 줄의 i번째 줄에 i번 접시의 가격 P_i와 종류 C_i가 공백으로 구분되어 주어진다. P_i와 C_i는 정수이며 1 ≤ P_i ≤ 10000, 1 ≤ C_i ≤ 3이다.

출력

조건에 맞는 꾸러미가 있으면 첫째 줄에 선택한 접시 번호 a, b, c를 a < b < c 순서로 출력하고, 둘째 줄에 세 접시의 가격 합을 출력한다. 조건에 맞는 꾸러미가 없으면 -1만 출력한다.

5 15
4 1
6 2
5 3
4 1
3 3

1 2 3
15

4 8
3 1
3 2
3 3
1 1

2 3 4
7

3 20
2 1
3 1
4 2

-1

출처: Devin.KR 자체 제작