마라톤 응원 거점

문제

마라톤 대회 운영진이 주로를 따라 응원 거점을 설치하려 한다. 설치할 수 있는 후보 지점은 출발점에서 가까운 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 후보에는 거점을 운영하는 데 필요한 비용과, 그곳에 거점을 설치했을 때 얻는 응원 점수가 정해져 있다. 운영진은 준비한 인력의 배치를 맞추기 위해 정확히 K개의 후보를 선택해야 한다. 응원 소리가 한 구간에 몰리는 일을 막기 위해 번호가 연속한 두 후보를 함께 선택할 수는 없다. 예를 들어 4번 후보를 선택하면 3번과 5번 후보는 선택할 수 없다. 이 제한은 후보 번호만으로 판단하며, 주로에서 두 후보 사이의 실제 거리는 따로 고려하지 않는다. 주로는 출발점과 도착점이 다른 길이므로 1번과 N번은 번호가 연속한 후보로 취급하지 않는다. 단, N이 2이면 두 후보의 번호가 실제로 연속하므로 함께 선택할 수 없다. 선택한 후보들의 운영 비용 합은 주어진 예산 B 이하여야 한다. 예산을 모두 쓸 필요는 없으며, 선택한 각 후보의 비용은 한 번씩만 더한다. 응원 점수도 선택한 후보들의 점수를 단순히 합한 값이다. 다른 후보의 선택 여부에 따라 특정 후보의 비용이나 점수가 달라지는 일은 없다. 운영진의 목표는 개수, 인접 제한, 예산 제한을 모두 지키면서 응원 점수의 합을 가장 크게 만드는 것이다. 후보는 많지 않지만 비용과 점수가 서로 다르므로, 점수가 높은 후보부터 고르는 것만으로는 항상 최선의 배치를 얻을 수 없다. 가능한 선택 중 최대 응원 점수를 구해야 한다. 같은 최대 점수를 만드는 선택이 여러 개여도 점수만 출력하며, 조건을 만족하는 선택 자체가 없으면 지정된 값 -1을 출력한다.

입력

첫째 줄에 후보의 개수 N, 선택할 개수 K, 예산 B가 공백으로 구분되어 주어진다. 모두 정수이며 1 ≤ N ≤ 24, 1 ≤ K ≤ N, 0 ≤ B ≤ 2,400,000을 만족한다.
다음 N개 줄 중 i번째 줄에 i번 후보의 운영 비용 C_i와 응원 점수 P_i가 주어진다. 두 값은 정수이며 1 ≤ C_i ≤ 100,000, 1 ≤ P_i ≤ 1,000,000을 만족한다.

출력

정확히 K개를 선택하고, 번호가 연속한 두 후보를 함께 선택하지 않으며, 총비용이 B 이하인 선택의 최대 응원 점수를 출력한다. 그러한 선택이 없으면 -1을 출력한다.

5 2 7
3 8
2 5
4 12
3 7
2 6

20

3 2 3
2 5
2 9
2 7

-1

출처: Devin.KR 자체 제작