당신은 어느 백화점의 쿠폰 2개를 받게 되었고, 쿠폰을 친한 친구의 생일 선물을 사기위해서 사용하고자 한다.

당신을 N 개의 물건들에 대해 조사하여 각각의 물건을 살 경우 드는 비용, 친구가 행복해할 정도, 그리고 물건을 반드시 사야 하는지를 규정하였다. 한 물건은 최대 한개만 살 수 있다. 동일한 물건을 여러번 사는 경우는 불가능하다.

1번 쿠폰의 경우 사려고 하는 물건 값의 합이 V1달러 이하의 선물들을 살 수 있다. 대부분의 쿠폰처럼 잔액이 남더라도 돌려 받지 못한다. 2번 쿠폰의 경우도 값이 V2인 것 빼곤 사용법이 동일하다. 두 쿠폰을 따로 사용하는 것은 가능하다. 허나 두 쿠폰의 액수를 합쳐 한 물건을 구매하는 것은 불가능하다.

그리고 이 백화점에선 생일인 사람의 선물을 사주려고 할 겨우, 물건 하나는 공짜로 살 수 있으며, 반드시 사야할 경우의 물건은 반드시 구매해야 한다. 물건들의 정보가 주어지고 쿠폰들의 액수가 주어졌을 때, 구매한 행복도의 합이 최대가 되는 조합을 찾는 프로그램을 작성하라.

#1518 upload 5 done 3 how_to_reg 3

쿠폰 timer 1s memory 32MB

#1518

쿠폰 1s 32MB