문제

현대모비스는 개의 자동차 공장을 가지고 있다. 공장은 번부터 번까지 번호가 매겨져 있고, 모든 자동차는 번 공장에서 조립이 시작되어서 번 공장에서 자동차 제작을 마무리하고 출고한다.

공장 간의 관계는 개의 정점과 개의 간선을 가진 단방향 그래프로 나타낼 수 있다. 각 정점은 공장을 의미하고, 간선은 번 공장에서 작업이 완료된 부품을 연결된 다음 공장으로 보내는 도로를 의미한다. 각 간선은 가중치를 가지고 있는데, 이는 그 도로를 이용해 보낼 수 있는 부품의 최대 개수를 의미한다.

예를 들어, 위 그림에서 개의 공장이 있다고 가정하면, 각 정점은 공장을 의미하고 간선은 번 공장에서 작업이 완료된 부품을 다음 공장으로 보내는 도로를 의미한다. 번 공장에서 작업을 완료했다면 번 공장 또는 번 공장으로 보낼 수 있다.

다음 공장으로 부품을 보낼 때 가중치에 적힌 값만 최대로 보낼 수 있다. 예를 들어, 위 그림에서 번 공장에서 작업이 완료된 부품을 번 공장으로 최대 개를 보낼 수 있다.

위 그림에서 한 개의 부품이 만들어질 때까지 경로와 한번에 만들 수 있는 부품의 개수를 계산해보면 아래 표와 같다.

개의 공장에서는 하나의 공장에서 출발하여 다시 해당 공장으로 돌아오는 사이클이 존재하지 않는다. 위 그림과 같이 번 공장에서 출발하여 순서대로 번 공장, 번 공장을 지나 다시 번 공장으로 돌아오는 경우는 없다는 것을 의미한다. 이를  라고 하며,  주어지는 그래프는 를 만족한다.

현대모비스는 출고하는 자동차의 수를 늘리고 싶어 예산 를 가지고 공장을 개선하려고 한다.  번 공장에서 번 공장으로 작업 완료된 부품을 보내는 도로가 있다면 보내는 부품의 수를 만큼 올릴 때 예산  만큼 사용한다. 도로를 무작위로 개선한다면 엉망진창이 될 수 있기 때문에 아래 규칙을 모두 만족하는 도로만 만들 수 있다.

1. 후보군 에 속한 공장끼리만 간선을 만들 수 있다
   
2. 처음 주어진 공장에서 모든 도로의 길이를 이라고 할 때, 번 공장에서 출발하여 번 공장으로 이동할 때 가능한 이동 거리 중 최댓값을 라고 한다. 만약 번 공장에서 번 공장까지 이동하지 못하는 경우는 이동 거리가 이라고 가정한다면,
   번 공장과 번 공장을 비교하여 를 만족하거나 를 만족하는 경우 번 공장에서 번 공장으로 부품을 보내는 도로를 만들 수 있다.
3. 번 공장에서 번 공장으로 부품을 보내는 경로를 만들려고 할 때, ,  둘 다 후보군 에 포함되어 있는 경우 번 공장에서 번 공장 또는 번 공장에서 번 공장으로 부품을 보내는 경로를 만들 수 있다.

예를 들어, 입력 예시 번과 같이 번 공장과 번 공장 사이에 도로가 존재하기 때문에 예산 을 소모하여 번 공장에서 번 공장으로 보내는 부품의 수를 만큼 증가할 수 있다. 이렇게 공장을 개선시키면 최대로 출고할 수 있는 자동차의 수는 대가 된다.

현재 주어진 예산 를 최대한 사용해서 공장을 개선할 때, 최대로 출고할 수 있는 자동차 수를 구하시오.

입력

첫째 줄에 공장의 개수 , 도로의 개수 , 예산 가 공백으로 구분되어 주어진다. (, , )

둘째 줄부터 개의 줄에 걸쳐 정수 , , 이 공백으로 구분되어 주어진다. 번 공장에서 번 공장으로 최대 대의 부품을 보낼 수 있다는 의미이다. (, )

번 줄에 후보군의 개수 가 주어진다. ()

번 줄에 개의 정수 가 공백으로 구분되어 주어진다. ()

주어지는 모든 입력은 정수이다.

출력

주어진 예산 를 최대한 써서 공장을 개선한다고 할 때, 최대로 출고할 수 있는 자동차 수를 출력하시오.

구름 블로그 방문하기

* 문제에 대한 힌트는 블로그에서 확인할 수 있습니다.

* 문제에 대한 질문은 Q&A에 남겨주세요!