메뉴 투어

라시드는 바르셀로나를 처음 방문했고 제대로 된 저녁 식사를 하고 싶다. 최고의 저녁 식사는 $C$개의 코스로 이루어지며, 코스에는 $1$번부터 $C$번까지 번호가 붙어 있고 반드시 번호 순서대로 먹어야 한다.

바르셀로나의 도로는 동서 방향 도로와 남북 방향 도로가 직교하는 규칙적인 격자를 이룬다. 도시에 식당이 $R$개 있고 모두 교차점에 있다. 교차점 $(i_1, j_1)$에서 교차점 $(i_2, j_2)$까지 걸어가는 데 걸리는 시간은 정확히 $|i_1 - i_2| + |j_1 - j_2|$분이다. 여기서 $(i, j)$는 서쪽에서 $i$번째 도로와 남쪽에서 $j$번째 도로가 만나는 교차점을 뜻한다.

식당이 모든 코스를 파는 것은 아니다. 식당 $k$가 코스 $c$를 판다면 가격은 $P[k, c]$유로다. $P[k, c] = 0$이면 그 식당은 그 코스를 팔지 않는다. 라시드가 저녁 식사에 쓸 수 있는 돈은 $B$유로다. 예산을 넘기지 않고 최고의 저녁 식사를 마칠 수 있는 식당 순서를 고르되, 식당 사이를 이동하는 총 시간을 최소로 하려고 한다. 투어는 아무 교차점에서나 시작하고 아무 교차점에서나 끝낼 수 있으며, 같은 식당을 여러 번 방문해도 된다.

그림의 예에서 코스는 세 개이고, 식당마다 코스 번호 순서대로 가격이 적혀 있다. -는 그 코스를 팔지 않는다는 뜻, 즉 $P[k, c] = 0$인 경우다. 예산이 $9$유로라면 최적 투어는 식당 $1, 4, 3$을 차례로 방문하는 것이고, 비용은 $6$유로, 총 이동 시간은 $12$분이다. 식당 $1, 2, 2$를 차례로 방문하면 이동 시간이 $2$분으로 더 짧지만 비용이 $17$유로여서 예산 $9$유로를 넘는다.

첫째 줄에 정수 $C$, $R$, $B$가 공백 하나로 구분되어 주어진다. 이어서 $R$개의 줄이 주어진다. $k$번째 줄은 $k$번 식당을 나타내고, 공백으로 구분된 $2 + C$개의 정수 $i[k]$, $j[k]$, $P[k, 1]$, $\dots$, $P[k, C]$로 이루어진다. $(i[k], j[k])$는 그 식당의 위치다.

제한

• $1 \le C \le 20$
• $1 \le R \le 100$
• $0 \le B \le 100$
• 모든 $1 \le k \le R$에 대해
  • $1 \le i[k] \le 1000$
  • $1 \le j[k] \le 1000$
  • 모든 $1 \le c \le C$에 대해 $0 \le P[k, c] \le 40$

정수 $y$ 하나를 출력한다. $y$는 라시드가 고를 수 있는 최적 식당 투어의 최소 총 이동 시간이다. 가능한 투어가 없으면 $-1$을 출력한다.