지하철

대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 회사에서 운영하고 있다. 두 회사는 경쟁 관계라서 사람들이 상대 회사의 지하철을 이용하는 것을 매우 싫어한다. 그래서 A와 B는 모두 상대 회사의 지하철로 환승할 때마다 비싼 요금을 받는다.

형욱이는 가난한 대학원생이기 때문에 돈을 아끼는 것이 가장 중요하다. 형욱이에게 최적의 출근 경로를 찾아주자. 최적의 출근 경로란 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로이다. 여기에서 환승은 이동하면서 지하철역을 운영하는 회사가 바뀔 때마다 1회로 계산한다.

위 그림에서 원은 지하철역을, 선은 지하철역들이 연결되어 있는지를 나타낸다. 흰색 지하철역은 A회사가 운영하는 역이고 검은색 지하철역은 B회사가 운영하는 역이다. 이때 붉게 표시된 경로로 이동하는 것이 환승 2회로 환승을 가장 적게 하면서 시간이 가장 짧은 경로이다.

첫째 줄에 지하철역의 수 N과 도착지의 번호 M이 공백을 사이에 두고 정수로 주어진다. 지하철역은 순서대로 0부터 N-1까지 존재하며 출발지는 항상 0이다. (2 ≤ N ≤ 1000, 0 < M < 1000)

그 다음 N 줄에 걸쳐 각 지하철역을 운영하는 회사의 정보 Ci(0 ≤ i < N)가 0 또는 1로 주어진다. 0은 A회사를, 1은 B회사를 뜻한다.

그 다음 N 줄은 지하철역 간의 연결 상태 Eij(0 ≤ Eij ≤ 1000)가 정수로 주어진다. Eij가 0이면 i번째 역과 j번째 역이 연결되어 있지 않음을, 0보다 크면 두 역이 연결되어 있으며 이동시간이 Eij임을 의미한다.

최적의 경로를 이용할 때 환승 횟수와 총 소요 시간을 공백으로 구분하여 출력한다.

출발지와 도착지는 반드시 연결되어 있음이 보장된다.