問題
정올나라에 N개의 도시(각 도시의 이름은 N번 도시이다)가 있고 각각의 도시에는 시장이 한 개씩 있다. 정올나라의 1번 도시에 사는 연준이는 M가지 물건의 심부름을 맡고 C원의 돈을 받았다. 그는 각 도시에 있는 시장에서 파는 물건들의 가격을 모두 알고 있다. 그리고 한 도시에서 다른 도시로 이동하는데 드는 비용은 T원이 든다는 것도 알고 있다. 연준이가 돈을 최대한 적게 쓸 때 소비할 돈을 알아내자.
入力
첫째 줄에는 도시의 개수 N(N≤10), 심부름할 물건 개수 M(M≤7), 받은 돈 C(C<1,000,000), 다른 도시로 이동하는데 드는 비용 T(T≤10,000)이 주어진다. 그리고 둘째 줄부터 N+1줄까지 각 시장에서 파는 물건의 비용이 주어진다. 각 시장의 물건은 왼쪽에서부터 순서대로 동일한 물건이다.
出力
물건을 굳이 순서대로 살 필요는 없고 물건을 모두 산 뒤에는 1번 도시로 다시 돌아가야 할 때 최저 비용을 출력한다. 만약 가지고 있는 돈으로 모든 물건을 살 수 없을 때는 "impossible"을 출력한다. 자세한 것은 출력 예를 참고한다.
例題 #1
4 3 2000 200
500 600 700
200 500 300
800 200 100
700 600 500
1100
例題 #2
2 4 3500 700
600 700 800 200
300 400 600 100
2300
例題 #3
3 2 700 400
200 800
300 400
100 100
impossible
出典
wlgjs0458
ログインしないとコードを書けません。