축제

음악 축제는 순수한 즐거움이어야 하지만, 어떤 축제는 너무 커져서 관람객에게 골칫거리가 된다. 문제는 너무나 많은 무대에서 너무나 많은 좋은 공연이 열리기 때문에, 어떤 공연을 볼지 고르는 단순한 일조차 복잡해진다는 것이다.

이런 축제의 관람객을 돕기 위해 Fulano는 애플리케이션을 만들기로 했다. 이 애플리케이션은 사용자가 즐겨 듣는 스트리밍 서비스에서 들은 노래를 평가한 뒤, 다음 기준에 따라 더 나은 공연 조합이 존재하지 않도록 볼 공연을 추천한다.

• 경험을 최대한 누리려면 고른 공연을 각각 끝까지 보는 것이 중요하다.
• 축제에 가서 어떤 무대도 보지 않는 것은 생각할 수 없다.
• 아티스트 선택이 사용자와 맞는지 확인하기 위해, 각 아티스트의 노래를 사용자가 스트리밍 서비스에서 들어서 아는 곡 수를 세었다. 고른 아티스트의 아는 곡 총합이 최대가 되어야 한다.

안타깝게도 애플리케이션의 베타 버전은 여러 비판을 받았다. 사용자가 추천받은 것보다 더 나은 선택을 생각해낼 수 있었기 때문이다. 이 문제에서 여러분의 과제는 Fulano를 도와, 각 무대에서 열리는 공연의 설명이 주어졌을 때 사용자에게 이상적인 목록을 계산하는 프로그램을 작성하는 것이다.

무대 사이를 이동하는 시간은 무시한다. 따라서 고른 두 공연의 시간이 조금도 겹치지 않으면 모두 끝까지 볼 수 있다고 본다. 특히 어떤 공연이 끝나는 순간 다른 공연이 시작되면 둘 다 볼 수 있다.

첫째 줄에는 무대의 수를 나타내는 정수 1 ≤ N ≤ 10이 주어진다. 다음 N개 줄은 각 무대에서 열리는 공연을 설명한다. i번째 줄은 i번째 무대에 예정된 공연의 수를 나타내는 정수 Mi ≥ 1로 시작하고, 이어서 Mi개의 공연 설명이 주어진다. 각 공연 설명은 3개의 정수 ij, fj, oj (1 ≤ ij < fj ≤ 86400, 1 ≤ oj ≤ 1000)로 이루어지며, 각각 공연의 시작 시각과 종료 시각, 그리고 공연하는 가수의 노래 중 사용자가 미리 들어서 아는 곡 수를 나타낸다. 모든 Mi의 합은 1000을 넘지 않는다.

고른 아티스트의 미리 들어서 아는 곡 총합을 나타내는 정수 하나를 한 줄에 출력한다. 유효한 해가 없으면 −1을 출력한다.