eolymp
bolt
Try our new interface for solving problems
Problems

The scientific project

The scientific project

Time limit 1 second
Memory limit 64 MiB

Научный проект состоит из N задач и выполняется на N-процессорном суперкомпьютере, каждая задача на одном из процессоров. Задачи могут выполняться параллельно с другими задачами, но некоторым из них необходимо иметь результаты некоторых других задач проекта. Для каждой задачи известно время, необходимое для её выполнения, и список предыдущих задач, которые должны быть завершены перед её запуском (этот список может быть и пустым).

Найти минимальное время, необходимое для выполнения всех N задач проекта, или вывести -1, если сделать это невозможно. Все входные числовые значения натуральны, не превышающие 100.

Input data

Первая строка - значение N, в последующих N строках - время и список предшествующих задач (если они есть) для каждой задачи.

Output data

Единственное число - минимальное время выполнения проекта или -1, если проект выполнить невозможно.

Examples

Input example #1
5
1 2 4 5
3
4 2 4
2
3 4
Output example #1
7