Majstor

Interview

Time limit3sMemory limit128 MB

Summary

Choose a prerequisite-closed set of jobs that maximizes total fee divided by total hours, with the quotient floored.

Level: Medium7 of 10
Topics: Greedy, Sorting, Graph, Binary search
Solved: No attempts yet

Problem

Majstor Rajko has $N$ jobs to do. The jobs are not independent: every job has a list of jobs that must be finished before that job can be started. For every job Rajko also knows how many hours it takes him and how many kuna he is paid for finishing it.

Rajko is lazy, so he decided to do only some of the jobs, picking the set that gives him the highest possible hourly rate. After that he quits and leaves on holiday with the money he earned.

Rajko computes the hourly rate by dividing the total fee of the jobs he did by the total number of hours he spent, discarding the remainder. He does at least one job.

Consider these four jobs.

Job number	Fee (kuna)	Duration (h)	Prerequisites
1	500	2	none
2	200	1	none
3	275	1	1, 2
4	600	2	2

If Rajko does all four jobs, his hourly rate is $(500 + 200 + 275 + 600) / (2 + 1 + 1 + 2) = 262$ kuna per hour. If he does only jobs 2 and 4, the rate is $(200 + 600) / (1 + 2) = 266$ kuna per hour, and no choice that respects the prerequisites beats that. Jobs 2, 3 and 4 alone would give 268 kuna per hour, but job 3 cannot be done until job 1 is finished.

Write a program that determines the highest achievable hourly rate.

Input

The first line contains an integer $N$ ( $1 \le N \le 100$ ), the number of jobs.

Each of the next $N$ lines describes one job. The description of job $i$ starts with three integers $H_i$ , $T_i$ and $P_i$ ( $1 \le H_i \le 1000$ , $1 \le T_i \le 10$ , $0 \le P_i < N$ ): the fee in kuna for finishing the job, the number of hours the job takes, and the number of jobs that must be finished before job $i$ . Then $P_i$ integers follow, the numbers of those jobs.

The prerequisites are always such that there is a way to finish every job.

Output

Print the highest achievable hourly rate in kuna on a single line. The rate is the total fee divided by the total hours with the remainder discarded, so the answer is an integer.

Examples3

Example 1

Input

4
500 2 0
200 1 0
275 1 2 1 2
600 2 1 2

Expected output

Example 2
Input
```
4
1 1 0
1 10 0
1000 1 0
1000 10 0
```
Expected output
```
1000
```

Example 3

Input

5
101 5 4 5 4 3 2
100 5 3 5 4 3
100 5 2 5 4
100 5 1 5
99 5 0

Expected output