기업 투자

한 투자자가 총 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보다 작습니다.