기업에 자금을 투자하면 기업은 그 자금으로 이익을 창출해 일정한 금액을 투자자에게 되돌려 준다. 기업이 여러 개가 있다면 가지고 있는 돈을 적절히 나누어서 투자하여 최대의 이익을 얻으면 된다. 어떤 기업에 자금을 투자하지 않으면 그 기업으로 부터는 당연히 얻게 되는 이익도 없다. 또, 한 기업에 더 많은 돈을 투자하면 적은 돈을 투자하는 것보다 더 많은 이익을 되돌려 준다.
M 원의 돈을 가지고 있는 투자가가 있다. 이 돈을 N 개의 기업에 적절히 나눠서 투자해 최대의 이익을 얻으려 한다. 이 때의 투자 방식과 이익금을 계산하는 프로그램을 작성하시오.
| A | B | C | |
| 0 | 0 | 0 | 0 |
| 1 | 2 | 1 | 3 |
| 2 | 5 | 4 | 4 |
| 3 | 7 | 9 | 9 |
| 4 | 8 | 11 | 10 |
M=4 , N =3 이고 이익이 왼쪽과 같을 때 최대 이윤은 12 이다.
입력 4 3 2 1 3 5 4 4 7 9 9 8 11 10 출력 12 0 3 1
출처: koi 중등부 기출