공부 계획하기
면접 대비시간 제한1초메모리 제한1024 MB
N개 과목에 총 T시간 이하로 공부 시간을 나눠 배정하고, 과목 점수 합에서 총 공부 시간에 따른 피로 감점을 뺀 값을 최대로 만드는 문제입니다.
문제
무대소녀 바나나는 고등학교 3학년이 되었다. 명문 대학에 가고 싶은 그녀이지만, 평소 연기 연습만 하고 내신 공부는 전혀 하지 않았다. 바나나는 정신을 차리고 시간 뒤에 있는 수능을 위해 공부하기로 마음먹었다. 그러나 공부 경험이 없는 바나나는 공부를 얼마나 해야 하는지 알 수 없었다. 바나나를 위해 공부 스케줄을 짜 주자!
수능에는 개의 과목이 있다. 번 과목을 총 시간 공부했을 때 받을 수 있는 점수를 라 하자. 바나나가 지켜온 스케줄에 따라, 각 과목의 공부 시간은 음이 아닌 정수여야 한다.
그러나 사람의 체력에는 한계가 있어 하루 종일 공부하는 것은 힘들다. 총 시간 동안 공부하면 피곤해져서 총 점수가 만큼 감소한다. 점수가 음수가 될 수도 있다.
최적의 방법으로 공부했을 때 바나나가 얻을 수 있는 최대 점수와 그때의 공부 방법을 구해야 한다.
입력
첫째 줄에 과 가 공백으로 구분되어 주어진다.
둘째 줄부터 번째 줄까지는 번째 줄에 번째 과목을 시간 공부했을 때 받을 수 있는 점수인 개의 수 가 공백으로 구분되어 주어진다.
번째 줄에는 개의 수 가 공백으로 구분되어 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
첫째 줄에 바나나가 받을 수 있는 최대 점수 를 출력한다.
둘째 줄에 각 과목별로 공부해야 하는 시간 을 공백으로 구분하여 출력한다. 최대 점수를 받는 공부 방법이 여러 가지라면, 그중 아무거나 출력해도 된다.
제한
- ;
- ;