집합을 만드는 마녀

큐베에는 발푸르기스의 밤을 앞두고 마녀 합성에 몰두하고 있다. 발푸르기스의 밤을 위해서는 특별한 그리프 시드(마녀의 알)를 사용해 구하기 쉬운 마녀를 잘 합성하여 목적인 무대 장치의 마녀를 만들어내야 하기 때문이다.

큐베에는 구하기 쉬운 종류의 마녀의 그리프 시드에서 마녀의 근원이 되는 것을 꺼내 빈 특별한 그리프 시드에 넣어, 그 그리프 시드에 마녀를 깃들게 할 수 있다. 또, 이 세계에는 어떤 조합으로 여러 마녀를 합성하면 새로운 1개의 마녀를 만들어낼 수 있다는 합성 법칙이 몇 가지 있다. 따라서 몇 개의 특별한 그리프 시드를 사용해 그 안에 있는 마녀의 근원이 되는 것을 합성하여 1개의 특별한 그리프 시드에 새로운 마녀를 깃들게 할 수 있다. 또, 합성한 결과 비게 된 특별한 그리프 시드는 재사용할 수 있다. 예를 들어, 3개의 특별한 그리프 시드에 든 마녀를 합성하면, 그 3개의 그리프 시드는 새로운 마녀가 깃든 1개의 특별한 그리프 시드와 2개의 빈 특별한 그리프 시드가 된다. 그러나 같은 종류의 마녀를 동시에 여러 그리프 시드에 넣을 수는 없다.

큐베에는 마녀를 특별한 그리프 시드에 깃들게 하고 마녀를 합성하는 것을 반복하여 무대 장치의 마녀를 만들어내고 싶다. 무대 장치의 마녀를 만들어내려면 특별한 그리프 시드가 몇 개 필요한지 구하라.

입력은 다음과 같은 형식으로 주어진다.

N E T
W1 W2 … WN
G1 C1 S1,1 S1,2 … S1,C1
G2 C2 S2,1 S2,2 … S2,C2
…
GE CE SE,1 SE,2 … SE,CE

N은 마녀의 종류의 개수, E는 합성 법칙의 개수, T는 무대 장치의 마녀의 번호이다. Wi는 i번째 마녀가 구하기 쉬운 마녀인지 나타내며, 1이면 구하기 쉬운 마녀, 0이면 구하기 쉬운 마녀가 아니다.

이어지는 E줄에 합성 법칙이 다음과 같이 주어진다. "번호가 Si,1 Si,2 … Si,Ci인 마녀를 합성하면 Gi번 마녀를 얻을 수 있다."

무대 장치의 마녀를 만들어내는 데 최소한 필요한 특별한 그리프 시드의 개수를 출력하라. 만들어낼 수 없으면 -1을 출력하라.

• 1<N≤300
• 0≤E≤1000
• 1≤T≤N
• 0≤Wi≤1 (1≤i≤N)
• 1≤Gi≤N (1≤i≤E)
• 2≤Ci≤10 (1≤i≤E)
• 1≤Si,j≤N (1≤i≤E, 1≤j≤Ci)
• {Gi,Si,1 Si,2 … Si,Ci}의 원소는 모두 다르다.
• 입력에 같은 합성 법칙이 2번 이상 나타나지 않는다.