문제
존은 H (1≤H≤16) 시간동안 N (2≤N≤25) 개의 호수를 다니며 낚시를 하려고 한다. 이 호수들은 일방통행 도로를 따라서 이동을 할 수 있다. 존은 1번 호수에서 시작해서 2번 호수로, 2번 호수에서 3번 호수로 이동하며 원하지 않는 호수는 지나갈 수 있고, 어떤 호수에서도 낚시를 그만두고 돌아갈 수 있다.
각 호수를 이동할 때는 5의 배수만큼 시간이 소요되며 Ti (0〈Ti≤192)로 표시한다. 이것은 i번째 호수에서 i+1번째 호수로 이동하는데 걸리는 시간이다. 예를 들어, T3 = 4는 3번 호수에서 4번 호수로 이동하는데 20분이 소요된다는 것을 의미한다.
존은 낚시 여행을 계획을 세우기 위해 호수에 대한 몇 가지 정보를 수집하고 있다. 각 호수 i에 대해, 최초 5분 동안 잡힐 것으로 예상되는 물고기의 수는 Fi (Fi≥0)로 나타낸다. 그 다음 5분마다 잡을 수 있는 물고기의 수는 Di(Di≥0) 만큼씩 줄어든다. 계획을 단순화하기 위해, 존이 잡는 물고기를 잡는 동안 다른 사람은 물고기를 잡지 안는다고 가정한다.
존이 잡는 물고기의 수를 최대화하기 위해 낚시 여행을 계획하는데 도움이되는 프로그램을 작성하시오. 단, 각 호수에서 보낸 시간은 5의 배수 이어야 한다.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 테스트 케이스의 첫줄에 호수의 개수 N, 2번째 줄은 여행 가능 시간 H, 3번째 줄에 n개의 Fi, 4번째 줄에 n개의 Di, 5번째 줄에 n-1개의 Ti가 들어온다. n에 0이 입력되면 입력이 끝난다.
출력
각 테스트 케이스 별로 각 호수에서 보낸 시간을 분단위로 쉼표로 구분하여 출력한다. 다음 줄에 최대로 잡은 물고기의 수를 예제와 같이 출력한다. 가능한 경우가 여러 가지라면 1번 호수에서 시간을 최대로 보내야 한다. 만약 이것도 같다면 2번, 그 다음 3번... 이어야 한다.
예제
2
1
10 1
2 5
2
4
4
10 15 20 17
0 3 4 3
1 2 3
4
4
10 15 50 30
0 3 4 3
1 2 3
0
45, 5
Number of fish expected: 31
240, 0, 0, 0
Number of fish expected: 480
115, 10, 50, 35
Number of fish expected: 724
로그인해야 코드를 작성할 수 있어요.