Jedi Academy
To become a Jedi, one must master both theoretical and practical skills. At the Jedi Academy, you can learn everything you need, provided you have the talent.
Phil, a new and gifted student at the academy, studies independently and can create his own schedule. He is very eager to learn, dedicating all his time to studying, except when he is moving between buildings or from the dormitory to a building.
The academy has two buildings: one for theoretical skills and another for practical skills. Traveling between these buildings takes exactly a minutes. Learning any skill takes exactly b minutes. Phil starts in the dormitory, and the journey from there to either building also takes a minutes.
Skills must be learned in a specific order. For example, before mastering the lightsaber, one must first learn the basics of optics and hand-to-hand combat. Phil finds it challenging to consider these prerequisites when planning his schedule.
Phil aims to become a Jedi as quickly as possible by learning all the necessary skills. Before he begins, he wants to know the minimum time required to complete his studies. Once he finishes, he will immediately go to fight evil, so he doesn't need to return to the dormitory.
Input
The first line of the input contains an integer n — the number of skills to be learned at the academy (1 ≤ n ≤ 10^5). All skills are numbered from 1 to n.
The next n lines describe the prerequisites for each skill. Each line starts with a number 1 or 2, indicating which building the skill can be learned in. This is followed by the number k — the number of prerequisite skills for skill i. Then, k integers follow, representing the skills required to learn skill i. It is guaranteed that the total number of prerequisites across all skills does not exceed 10^5.
The following line contains two integers a — the time in minutes to travel between buildings or from the dormitory to a building, and b — the time to learn one skill (1 ≤ a, b ≤ 10^4).
It is guaranteed that there exists a learning order for all skills such that each skill is learned only after all its prerequisites have been completed.
Output
Output a single line with the minimum time in minutes that Phil will need to become a Jedi.