여러 명의 탐험가들이 어두운 동굴의 입구에 서있다. 이 사람들은 모두 동굴을 통과해서 출구에 다 같이 서 있으려고 한다. 불행하게도 여러 상황이 겹쳐서 다 같이 동굴을 통과하는 것이 불가능하게 되었다. 따라서, 작은 그룹으로 나눠서 동굴을 통과해야 한다. 그리고, 지도는 단 한 개 뿐인데, 동굴을 지도 없이 다닌다는 것은 불가능하다. 따라서 동굴 안에 있는 그룹은 그 그룹 내에 있는 한 명이 지도를 가지고 있어야 한다.</p>

탐험가 그룹이 동굴에 들어가서, 출구를 향해 갈 때, 낡은 다리를 건너야 한다. 그룹에 있는 모든 사람은 반드시 동시에 다리를 건너야 한다. 낡은 다리는 B 킬로그램까지 지탱할 수 있다. 그걸 넘으면 붕괴할 것이다.

탐험가는 혼자서 동굴에 들어 갈 수 있다. 또, 두 명 또는 그 이상이 그룹으로 같이 동굴에 들어갈 수 있는데, 이때 그룹 내에 존재하는 각각의 탐험가는 그룹원 중 적어도 한 명은 믿어야 한다.

탐험가는 모두 다른 속도로 걷는다. 그러나 그들이 동굴에 들어갔을 때는 모두 같은 속도로 걸어야 한다. 따라서, 탐험가 그룹이 동굴에 들어갔을 때는, 그 그룹에서 가장 느린사람의 속도로 다같이 걷게 된다.

탐험가들이 모두 동굴을 통과하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 탐험가의 수 N이 주어진다. N은 13보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각각의 탐험가의 무게와 걷는 시간이 주어진다. 두 수는 모두 1,000보다 작거나 같은 자연수이다. 그 다음 줄부터 N개의 줄에는 탐험가들 사이의 신뢰표가 주어진다. 이 신뢰표에서 i번째 줄 j번째 열이 의미하는 것은 탐험가 i번이 탐험가 j를 신뢰하는지 안 하는지이다. 여기에서는 Y또는 N만이 들어오며, i번째 줄 i번째 행은 항상 Y이다. 꼭 대칭일 필요는 없다. 그리고 마지막 줄에는 다리가 지탱할 수 있는 무게의 한계 B가 주어진다. B는 5,000보다 작거나 같은 자연수이다.

출력 형식

첫째 줄에 탐험가가 모두 다리를 건너는데 걸리는 시간의 최솟값을 출력한다. 탐험가가 모두 다리를 건널 수 없을 때는 -1을 출력한다.

예제 입력 1

3
1 2
1 3
1 4
YYY
YYY
YYY
2

예제 출력 1

9

예제 입력 2

3
1 2
1 3
1 4
YYY
YYY
NYY
2

예제 출력 2

10

예제 입력 3

3
1 7
1 13
1 19
YYN
NYY
YNY
3

예제 출력 3

19

예제 입력 4

1
43 23
Y
42

예제 출력 4

-1

힌트

예제 1의 경우 1번 탐험가와 3번 탐험가가 동시에 출발한다. 출구까지 간다. (4 걸림) 1번 탐험가가 입구로 혼자 돌아온다. (2 걸림) 1번 탐험가가 2번 탐험가와 함께 출구로 간다. (3)