기업 투자
시간 제한1초메모리 제한128 MB
각 회사에 정수 단위로 투자했을 때의 수익표가 주어질 때, 총 N단위를 정확히 나눠 최대 수익을 얻는 배분을 구하는 냅색형 DP 문제입니다.
문제
한 투자자가 총 N만 원을 M개 기업에 만 원 단위로 나누어 투자하려고 합니다. 각 기업에 x만 원을 투자했을 때 얻는 이익이 표로 주어집니다. x=0이면 이익은 0입니다.
각 기업에 투자하는 금액은 정수 만 원 단위여야 하며, 투자 금액의 합은 정확히 N만 원이어야 합니다. 얻을 수 있는 최대 이익과 그때 각 기업에 투자할 금액을 구하세요.
입력
첫째 줄에 총 투자 금액 N과 기업 수 M이 주어집니다. (1 <= N <= 300, 1 <= M <= 20)
다음 N개의 줄에는 투자액 x와, 1번 기업부터 M번 기업까지 각각 x만 원을 투자했을 때 얻는 이익이 차례로 주어집니다. 각 x는 1 이상 N 이하이며 서로 다릅니다.
출력
첫째 줄에 얻을 수 있는 최대 이익을 출력합니다.
둘째 줄에는 1번 기업부터 M번 기업까지 투자한 금액을 공백으로 구분해 출력합니다. 최대 이익은 2^31보다 작습니다.