27116번 - 전투기 출격

공군의 특급 조종사 하늘이가 임무 수행을 위해 전투기 출격 준비를 마쳤다!

임무 구역은 $1$번부터 $M$번까지의 번호가 붙어 있으며, 모든 구역은 각각 $i$번 구역에서 $j$번 구역으로 가는 거리 $d_{ij}$의 항로로 연결되어 있다. 하늘이가 조종하는 전투기는 비행한 거리만큼의 연료를 소모하며, $i$번 구역에 착륙하는 데에는 $f_i$만큼의 연료를 추가로 소모한다.

이번 임무에서 하늘이는 초기 위치인 $1$번 구역에서 출발하여 길이 $N$의 비행경로를 순서대로 순회하되, 주어진 길이 $N$의 비행경로 중 하나의 구역에 착륙하여 지상 임무를 수행한 뒤 다시 이륙하여 남아 있는 비행경로를 모두 순회해야 한다. 이때, 필요하다면 비행경로에 포함되지 않은 구역을 경유하며 순회하는 것도 가능하다.

그러나 전투기 출격 직전에 하늘이는 이 임무를 모두 완수하기에 현재 전투기에 남아 있는 연료의 양이 부족할 수도 있다는 사실을 깨달았다. 따라서 하늘이는 중간에 착륙하여 지상 임무를 수행하는 도중에 동료 조종사를 호출하고자 한다. 호출을 받은 동료 조종사는 하늘이가 지상 임무를 수행 중인 구역의 다음 구역부터 연속한 몇 개의 비행 구역을 대신 순회해준다. 물론 동료 조종사를 호출하지 않고도 모든 임무 구역을 순회할 수 있다면 동료 조종사를 호출하지 않아도 된다. 이때, 동료에게 폐가 되지 않도록 동료 조종사가 순회하는 구역의 개수를 최소화하고자 한다. 또한, 만약 동료 조종사가 순회하는 구역의 개수를 최소화하는 방법이 여러 가지라면, 그중 연료를 가장 적게 사용하는 방법으로 비행하고자 한다.

하늘이를 위해, 동료 조종사가 순회하는 구역의 최소 개수와 그때 사용하는 연료의 최솟값을 구해주자.

첫 번째 줄에 전체 비행경로의 길이 $N$, 전체 구역 개수 $M$, 전투기에 남아 있는 연료 $R$가 공백으로 구분되어 주어진다. $(1\leq N\leq 100\,000;$ $3\leq M\leq 100;$ $1\leq R\leq 10^9)$

두 번째 줄부터 $M+1$번째 줄까지, $i+1$번째 줄에 $i$번 구역에서 $j$번 구역으로 가는 항로의 거리 $d_{ij}$가 공백으로 구분되어 주어진다. $(0\leq d_{ij}\leq 10^9;$ $i=j$인 경우 $d_{ij}=0)$

$M+2$번째 줄에 $M$개의 구역에 착륙할 때 드는 연료량 $f_i$가 공백으로 구분되어 주어진다. $(0\leq f_i\leq 10^9)$

$M+3$번째 줄에 비행경로를 나타내는 $N$개의 정수 $a_i$가 공백으로 구분되어 주어진다. $(1\leq a_i\leq M)$

비행경로에 동일한 구역이 연속으로 있는 경우도 주어질 수 있음에 유의하라.

동료 조종사가 순회하는 구역의 최소 개수와 그때 소모하는 연료의 최솟값을 공백으로 구분하여 출력한다.

만약 $R$ 이하만큼의 연료를 소모하여 임무를 완수하는 것이 불가능하다면, $-1$을 출력한다.

$1$번 구역에서 $3$번 구역으로 갈 때, $1$번에서 $3$번 구역으로 곧장 가는 것보다 $2$번 구역을 경유하여 가는 것이 거리가 더 짧은 것에 유의하여라.

또한, 하늘이는 지상 임무를 수행하는 도중에 동료 조종사를 호출하므로, 비행경로의 첫 번째 구역은 동료 조종사가 대신 순회해 줄 수 없음에 유의하여라.