튜브의 소개팅

얼마 전 소개팅에 실패해 낙담한 튜브를 안타깝게 여긴 친구들은 튜브에게 새로운 사람을 소개해주기로 했다. 좀 더 자연스러운 자리를 만들기 위해, 튜브와 소개팅녀를 파티에 초대하기로 했다.

친구들은 튜브에게 파티에 초대된 모든 사람의 위치를 알려주었다. 사각형 모양의 파티장 입구는 왼쪽 맨 위였고, 만나야 하는 상대의 좌석은 파티장의 오른쪽 맨 아래였다. 파티장의 가로 길이가 n이라고 하고, 세로 길이를 m이라 할 때, 튜브와 소개팅 상대의 위치는 각각, (0, 0), (m - 1, n - 1)이 된다.

튜브는 (0, 0)에서 (m - 1, n - 1)까지 가는 가장 짧은 길을 알고 싶다. 이동은 좌/우/상/하로만 가능하다. 또한, 조금이라도 더 빠르게 이동하고 싶은 튜브는 이동하는 중에 가능한 덜 수다스러운 친구들만 만나고 싶다. 다시 말해, 목표 지점까지 길이가 같은 여러 개의 경로가 존재할 경우, 경로상에 위치한 친구들과 나눠야 하는 대화 시간의 합이 적은 것을 더 선호한다.

튜브에게는 스트레스를 심하게 받을 경우 미친 오리로 변하는 비밀이 있다. 경로 상에 위치한 친구들과 나눠야 하는 대화 시간의 합이 s를 초과한다면 미친 오리로 변하고 소개팅에 실패하고 말 것이다! 그러므로 아무리 짧은 경로라도 친구들과 나눠야 하는 대화 시간의 합이 s를 초과한다면 그 경로를 진행할 수는 없다.

튜브가 소개팅 상대에게 무사히 갈 수 있는 경로를 알려주자.

입력 형식

입력은 파티장의 크기 m과 n 그리고 튜브가 참을 수 있는 대화 시간의 총합 s, 친구와의 대화에 필요한 시간 t가 담긴 2차원 배열 time_map으로 주어진다. t가 -1인 경우는 파티 테이블이 위치한 경우라 지나갈 수 없다. 그리고 시작 지점과 도착 지점에서는 수다에 필요한 시간이 없다, 즉 t = 0이다.
추가 제한조건은 아래와 같다.

• 2 <= n, m <= 50
• 1 <= s <= 2^31-1
• -1 <= t <= 2^31-1
• 모든 입력에는 문제의 조건을 만족하는 경로가 하나 이상 존재한다.

출력 형식

리턴 타입은 원소가 두 개인 정수 배열이다. 튜브가 이동해야 하는 경로의 길이와 해당 경로를 지나갈 때 친구와 나눠야 하는 대화 시간의 총합을 리턴한다.

예제 입출력