정올국엔 0번부터 (n-1)번까지 지정되어 있는 총 n개의 도시가 있다. 이는 m개의 양방향 도로로 연결되어 있다. 어떤 두 도시 i, j를 뽑더라도 i번 도시부터 j번 도시까지 직접 또는 다른 도시를 경유해서 가는 경로는 무조건 존재한다.

정올국의 대규모 도로 포장 정책으로, 모든 도로는 새것이 되었다. 그래서 초기에, 모든 도로의 부식도는 0이다. 화물 트럭이 한번 지나갈 때마다, 그 도로의 부식도는 1씩 증가한다.

정올국은 아직 t번의 도로 수리를 더 해줄 수 있는 예산이 있다. 한 번 수리할 때 마다, 도로의 부식도는 1씩 감소한다. 한 도로를 여러 번 수리하는 것도 가능하다.

화물 트럭의 내구도는 거쳐왔던 도로 중 가장 높은 부식도를 가진 도로의 부식도 만큼 감소한다. 내구도 감소가 클수록, 트럭의 질이 떨어진다.

철기는 정올 우체국택배의 매니저이다. 철기의 목표는 k개의 트럭을, 0번 도시부터 n-1번 도시까지 보내는 것이다. 철기는 k개의 트럭 중 내구도가 가장 많이 감소한 트럭의 내구도 감소가 최소화될 수 있도록 하고 싶다.

철기를 도와 k개의 트럭 중 최대로 내구도가 감소한 트럭이 최소의 피해를 입는 경우, 그 최대 내구도 감소도를 출력하는 프로그램을 작성하라.

화물 트럭 timer 2s memory 256MB

화물 트럭 2s 256MB