Академия Джедаев
Чтобы стать джедаем, необходимо овладеть многими теоретическими и практическими навыками. В Академии Джедаев можно обучиться всему необходимому, если, конечно, у тебя есть способности.
Новый студент академии Фил очень способный и обучается индивидуально. Он вправе самостоятельно составлять своё расписание. Фил очень любознателен, поэтому он всё своё время посвящает учебе. Фил не учится только в те моменты, когда переходит из одного корпуса академии в другой или идёт из общежития в один из корпусов.
Академия состоит из двух корпусов, в одном из которых обучают теоретическим навыкам, а в другом — практическим. Путь из одного корпуса в другой занимает ровно a минут. Изучение любого навыка занимает ровно b минут. В начальный момент Фил находится в общежитии, путь от которого до каждого из корпусов также занимает a минут.
Разумеется, навыки нельзя изучать в произвольном порядке. Например, прежде чем овладеть световым мечом, нужно сначала изучить основы оптики и искусство рукопашного боя. Филу важно учесть это при составлении своего расписания.
Фил хочет как можно скорее стать джедаем, но для этого ему нужно обучиться всем необходимым навыкам. Прежде чем приступить к учебе, он хочет узнать через какое минимальное число минут он сможет изучить все навыки. Помогите ему это выяснить. После окончания учебы Фил сразу же отправится сражаться со злом, возвращаться в общежитие ему не требуется.
Входные данные
В первой строке входного файла задано целое число n — количество навыков, которым нужно обучиться в академии (1 ≤ n ≤ 10^5). Все навыки пронумерованы от 1 до n.
В следующих n строках описаны требования для изучения каждого навыка. В начале i-й из этих строк записано число 1 или 2, оно указывает в каком корпусе можно изучить i-й навык. Затем следует число k —количество навыков, необходимых для изучения навыка i. Затем в этой же строке следует k целых чисел — навыки, необходимые для изучения навыка i. Гарантируется, что сумма чисел k по всем навыкам не превосходит 10^5.
В следующей строке задано два целых числа a — время в минутах на путь из одного корпуса в другой или из общежития до корпуса, и b — время на изучение одного навыка (1 ≤ a, b ≤ 10^4).
Гарантируется, что существует такой порядок изучения всех навыков, при котором каждый раз при изучении очередного навыка все необходимые для него уже изучены.
Выходные данные
В единственной строке выходного файла выведите минимальное время в минутах, которое потребуется Филу, чтобы стать джедаем.