기업투자 > 문제은행



1825 : 기업투자

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
931 회   
시도횟수
2618 회   
spj

문제

어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 

단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 

돈을 투자하지 않은 경우는 당연히 얻게 되는 이익도 없다. 

예를 들어서, 한 투자가가 4만원을 갖고 두 개의 기업들에 각각 만원 단위로 투자했을 경우 얻을 수 있는 이익은 다음과 같다.

 

29b5582f5bcd30729e8bdfdf63fa7d85_1506820
 

 

위의 경우 만일, 기업 A에 1만원, 기업 B에 3만원을 투자하는 경우 투자가가 얻는 이익은 14만원(5만원+9만원)이다. 
4만원을 투자해서 가장 많은 이익을 얻을 경우 기업 B에만 4만원을 투자하는 경우로서 이때의 이익은 15만원이다. 
여기서 투자가는 한 기업에 돈을 나누어 투자할 수는 없다. 

 

 

투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 경우에 얻게 되는 이익이 주어졌을 때 

가장 많은 이익을 얻을 수 있는 투자방식과 이때의 이익금을 구하는 프로그램을 작성하라.

 


입력형식

첫 줄은 투자 금액과 투자 가능한 기업들의 개수이며, 둘때 줄부터 각 줄은 투자액수 및 각 기업이 투자가에게 주는 이익이다. 단, 총 투자금액은 300만원을 넘지 않으며, 투자 가능한 기업의 개수는 최대 20개이다.

출력형식

첫 줄에 얻을 수 있는 최대 이익을 출력하고, 둘째 줄에는 각 기업에 투자한 액수를 출력한다.

입력 예

4 2
1 5 1
2 6 5
3 7 9
4 10 15

출력 예

15
0 4


다이나믹

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP