E. The Great Karpish Bake Off
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp has entered the Karpish Bake Off with his magnum opus, Tres Peces, and the hungry judges expect it by time $$$T$$$.

To prepare his masterpiece, he has $$$n$$$ recipes, numbered $$$1,2,\ldots,n$$$, with recipe 1 being his Tres Peces. Recipe $$$i$$$ takes $$$t_i$$$ units of time and can begin only after its $$$m_i$$$ prerequisite recipes finish, while recipes without prerequisites can begin at time $$$0$$$.

The dependencies form a tree rooted at recipe $$$1$$$, meaning that every other recipe is a prerequisite of exactly one recipe and all recipes are needed for recipe $$$1$$$. Since Magikarp has unlimited KI (Karpificial Intelligence) agents, any number of recipes can be prepared in parallel.

Some of his recipes are also boostable. This means that Magikarp can choose one positive integer power level $$$x$$$ before cooking begins, which changes the duration of every boostable recipe to $$$$$$ \left\lfloor\frac{t_i}{x}\right\rfloor $$$$$$ units of time, while other recipes still take $$$t_i$$$ units of time.

Find the minimum power level such that Magikarp can finish his Tres Peces by time $$$T$$$, or determine that this is impossible.

Input

The first line contains two integers $$$n$$$ and $$$T$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$0\le T\le 10^{14}$$$) — the number of recipes and the deadline, respectively.

The second line contains $$$n$$$ integers $$$t_1,t_2,\ldots,t_n$$$ ($$$1\le t_i\le 10^9$$$) — the preparation times before boosting.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$b_i\in\{0,1\}$$$), where $$$b_i=1$$$ if recipe $$$i$$$ is boostable and $$$b_i=0$$$ otherwise.

The $$$i$$$th of the next $$$n$$$ lines contains an integer $$$m_i$$$ ($$$0\le m_i\le n-1$$$), followed by $$$m_i$$$ distinct integers $$$a_{i,1},a_{i,2},\ldots,a_{i,m_i}$$$ ($$$1\le a_{i,j}\le n$$$) — the number of prerequisite recipes and their recipe numbers, respectively.

Output

Output a single integer — the minimum positive integer power level such that Magikarp can finish his Tres Peces by time $$$T$$$, or -1 if this is impossible.

Examples
Input
3 6
3 8 5
0 1 1
2 2 3
0
0
Output
3
Input
2 3
4 10
0 1
1 2
0
Output
-1
Input
1 0
7
1
0
Output
8
Note

In the first example, recipes $$$2$$$ and $$$3$$$ are prepared in parallel before recipe $$$1$$$ begins. At power level $$$2$$$, recipe $$$1$$$ finishes at time $$$4+3=7$$$ and misses the deadline, whereas power level $$$3$$$ lets it finish at time $$$2+3=5$$$, so the answer is $$$3$$$.

In the second example, recipe $$$1$$$ alone takes $$$4$$$ units of time and cannot be boosted, so the deadline of $$$3$$$ is impossible.

In the third example, power level $$$8$$$ reduces the duration to $$$\lfloor\frac{7}{8}\rfloor=0$$$, while every smaller positive power level takes at least one unit of time.