Majstor

수리공 Rajko는 일 $N$개를 해야 한다. 일은 서로 독립이 아니다. 각 일에는 그 일을 시작하기 전에 반드시 끝나 있어야 하는 일의 목록이 있다. 또 일마다 Rajko가 그 일을 끝내는 데 걸리는 시간과, 끝냈을 때 받는 금액이 쿠나 단위로 정해져 있다.

Rajko는 게을러서 몇 개의 일만 골라 하기로 했다. 고르는 기준은 시급이 가장 높아지는 것이다. 그다음에는 일을 그만두고 번 돈을 들고 휴가를 떠난다.

Rajko는 자기가 한 일의 보수를 모두 더한 값을 쓴 시간의 합으로 나누고 나머지를 버려서 시급을 구한다. Rajko는 적어도 일 한 개는 한다.

다음 네 개의 일을 보자.

Rajko가 네 일을 모두 하면 시급은 $(500 + 200 + 275 + 600) / (2 + 1 + 1 + 2) = 262$ 쿠나다. 2번과 4번만 하면 시급이 $(200 + 600) / (1 + 2) = 266$ 쿠나이고, 선행 조건을 지키면서 이보다 높은 시급을 얻는 방법은 없다. 2번, 3번, 4번만 하면 시급이 268 쿠나가 되지만, 1번을 끝내지 않고서는 3번을 할 수 없다.

가장 높은 시급을 구하는 프로그램을 작성하시오.

첫 줄에 일의 개수 $N$ ($1 \le N \le 100$)이 주어진다.

다음 $N$개의 줄에는 일 하나의 정보가 주어진다. $i$번째 일의 정보는 정수 $H_i$, $T_i$, $P_i$ ($1 \le H_i \le 1000$, $1 \le T_i \le 10$, $0 \le P_i < N$)로 시작한다. 각각 그 일을 끝냈을 때 받는 보수(쿠나), 그 일에 걸리는 시간, $i$번째 일보다 먼저 끝나야 하는 일의 개수다. 이어서 그 일의 번호가 $P_i$개 주어진다.

선행 조건은 항상 모든 일을 끝낼 수 있도록 주어진다.

첫 줄에 가능한 가장 높은 시급을 쿠나 단위로 출력한다. 시급은 보수의 합을 시간의 합으로 나눈 뒤 나머지를 버린 값이므로 정수다.