단체를 위한 파리 관광

PSG(Paris Sightseeing for Groups)에서의 새 직장에 오신 것을 환영한다. PSG의 다른 모든 직원과 마찬가지로, 당신은 여러 사람의 단체를 위한 여행을 계획하는 일을 맡는다. 당신의 급여는 “고객 점수”에 따라 결정된다. 이 “고객 점수”는 당신의 여행에 h 이상의 점수를 준 단체가 h개 이상 존재하도록 하는 최대의 h로 계산된다.

당신은 각 단체의 취향에 맞춰 여러 개의 여행을 준비했다. 각 단체가 각 여행을 얼마나 좋아할지는 미리 알고 있다. 그러나 어떤 선택지는 시간이 더 많이 들고, 어떤 선택지는 비용이 더 많이 든다. 일주일에 100시간을 일할 수 없고 예산도 한정되어 있으므로, 각 단체마다 가장 좋아하는 여행을 선택하는 것만으로 “고객 점수”를 최대화할 수는 없다.

당신은 시간과 금액 예산을 고려했을 때 달성할 수 있는 최대 고객 점수를 알려주는 프로그램을 원한다. 각 단체마다 정확히 하나의 여행을 계획해야 한다는 점에 유의하라!

입력은 여러 줄로 이루어지며, 각 줄은 하나의 공백으로 구분된 정수들로 구성된다.

• 첫 번째 줄에는 세 개의 정수가 주어진다.

  • N: 단체의 수
  • Mtot: 보유한 총 금액
  • Ttot: 방문에 할당된 총 시간

• 이어서 N개의 단체가 여러 줄에 걸쳐 설명된다.

  • 첫 번째 줄에는 i번째 단체의 선택지 수 Pi가 주어진다.
  • 이 줄 다음에는 Pi개의 줄이 오며, 각 줄에는 i번째 단체의 j번째 선택지를 설명하는 세 개의 정수 Mi,j, Ti,j, Si,j가 주어진다. Mi,j는 필요한 금액, Ti,j는 방문에 걸리는 시간, Si,j는 점수이다.

출력은 한 줄로 이루어지며, 그 내용은 정수 h이다. 이는 h개 이상의 단체에 h 이상의 점수를 줄 수 있도록 하는 최대의 h이다. 각 단체마다 여행을 계획하는 것이 불가능하면 출력은 −1이다.

• 0 ≤ Mi,j ≤ Mtot ≤ 2 500
• 0 ≤ Ti,j ≤ Ttot ≤ 2 500
• 0 ≤ Si,j ≤ 2 500
• 1 ≤ Pi ≤ 5
• 3 ≤ N ≤ 100