h(1<= h <=16) 시간의 여유시간이 있어 고기를 잡으러 호수에 간다.

호수는 1 번 호수 에서 2 번 호수로 연결되어 있고 2 번 호수에서 3 번 호수로 연결되어 있다. 각 도로는 일방통행로이고 호수의 수 n ( 2 <=n <= 25)이 주어진다. 항상 1 번호수에서 낚시를 시작하고 원하지 않은 호수는 그냥 지나칠수도 있고 어떤 호수에서도 낚시를 끝낼수 있다.

호수로 이동하는데는 5 의배수 만큼의 시간이 소요되는데 ti( 0 < ti <= 192) 시간이란 i 번째 호수에서 i+1 번째 호수로 이동하는데 걸리는 시간을 의미한다. 즉 3 번 호수에서 4 번 호수로 이동하는데 20 분(5*4)이 소요되는 경우 t3 = 4 라고 표기한다.

호수 i 에서 최초 5 분간 잡을 수 있는 고기의 수는 fi 로 , 매 5 분 마다 잡을 수 있는 고기는 일정한 수 di 만큼 줄어든다. 계획을 단순화 하기 위하여 , 다른 사람이 고기를 잡더라도 존이 잡히는 고기는 영향이 없고 , 호수에 머무는 시간은 5 의 배수라 하자.

최대로 고기를 잡을 수 있도록 하는 프로그램을 작성하시오.

입력

• 호수의 수 n 으로 시작한다.
• 다음 라인은 가용한 시간 h 가 주어지고
• 다음 라인에는 n 개의 정수 fi 가
• 다음 라인은 n 개의 정수 di 가 주어지고 ,
• 마지막으로 n - 1 개의 정수 ti 가 주어진다.

예를 들어 ,

2 -- 호수 수 
1 -- 1 시간 가용 
10 1 -- fi(최초 5 분간 잡을 수 있는 고기수) 
2 5  -- di(5 분 지날 때 마다 줄어드는 고기수)
2    -- ti(호수를 이동하는데 걸리는 시간)

출력

만약 여러가지 플랜이 존재하면 1 번 호수 에서 보내는 시간이 최대가 되도록 하고 , 이 것도 같다면 2 번 호수에서 보내는 시간이 최대가 되도록...

입출력 예

입력

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

출처: East Central North America 1999