Problem G: Sports Days

会津大学附属小学校（会津大小）は日本有数の競技プログラマー養成校として有名である。 もちろん、運動会に参加しているときでさえアルゴリズムの修行を欠かせない。

競技プログラミング部部長のあなたはもちろんこの大会でも勝利したい。 今回はある競技に注目する。

ある競技とは会津大小で行われている伝統的な競技だ。 校庭にコーンがn個置いてある。 コーンは4色用意されている。 コーンのいくつかのペアは白線で描かれた矢印で結ばれている。 矢印は片側だけについており、整数が併記されている。

競技者はk人1チームとして行動する。 あるスタート地点のコーンからゴール地点のコーンまで矢印の上をその向きに移動する。 ただし、k人それぞれがゴール地点までの経路は異なる必要がある。

経路1と経路2が異なるというのは、

• 条件1　経路1と経路2で経由する矢印の本数が等しい場合、経路1でi番目に経由する矢印と経路2でi番目に経由する矢印が異なるようなiが存在すること。
• 条件2　経路1と経路2で経由する矢印の本数が異なっていること。

のいずれかを満たせば経路が異なっていると言える。

さらに、コーンの辿り方には禁止された色のパターンがあり、スタート地点からゴール地点までの経路でそのパターンを含んでしまった選手はリタイアとなる。 ただし、それ以外の経路はどのような経路を辿ってもよく、何度も同じコーン（スタート地点やゴール地点のコーンを含む）を通って良い。 また、矢印に併記された数字がスコアとして加算されていく。 この競技はより多くのチームメイトがより小さな合計スコアでゴール地点のコーンに辿りつけたチームが勝利となる。

部長のあなたはもちろんプログラミングでこの問題を解決できるはずだ。 ゴールまで移動可能な最大の人数を求めよ。 また、最大人数で辿り着いた時の最小スコアを求めよ。

ただし、いくらでもスコアを小さく出来る場合は -1 を出力せよ。

Input

入力は複数のテストケースから成り立っている。 テストケースの数は20ケースを超えない。

n
col1
col2
...
coln
m
a1 b1 c1
a2 b2 c2
...
am bm cm
k
pattern

n( 2 ≤ n ≤ 100)はコーンの数を表す。 col_i(1 ≤ col_i ≤ 4)はi番目のコーンの色を示す。 m(0 ≤ m ≤ 1,000) は矢印の数を表す。 a_i は矢印の始点のコーンの番号, b_iは終点のコーンの番号を表し、c_iはその矢印のスコアを表す. また、ひとつのコーンから伸びる矢印は10本までである。 (1 ≤ a_i, b_i ≤ n, -1,000 ≤ c_i ≤ 1,000) kは競技を行うチームの人数を示す。 (1 ≤ k ≤ 10) pattern は長さが10以下の1~4までの数字からなる文字列で、 移動が禁止されているパターンを示す。 スタート地点のコーンは1番目のコーンであり、 n番目のコーンがゴールである。 入力で与えられる数(n, col, m, a, b, c, k)はすべて整数である。 入力の終わりは0を含む1行で示される。

Output

出力は空白で区切られた二つの整数からなる。 1つ目は到達できる人数で、2つ目はその最小コストである。 もし、いくらでもスコアを小さく出来る場合は-1のみを含む１行を出力せよ。 一人も到達できない場合は0 0を出力せよ。

Sample Input

2
1
1
2
1 2 1
2 1 1
1
1111
2
1
1
2
1 2 1
2 1 1
1
11
2
1
1
2
1 2 1
2 1 1
10
1111
2
1
1
2
1 2 1
2 1 1
10
111111
2
1
1
2
1 2 -1
2 1 0
10
11
2
1
1
2
1 2 -1
2 1 0
10
1111
2
1
1
2
1 2 -1
2 1 0
10
12
2
1
1
2
1 2 -1
2 1 0
10
1111111111
0

Sample Output

1 1
0 0
1 1
2 4
0 0
1 -1
-1
4 -10