Problemas
당신은 어느 백화점의 쿠폰 2개를 받게 되었고, 쿠폰을 친한 친구의 생일 선물을 사기위해서 사용하고자 한다.
당신을 N 개의 물건들에 대해 조사하여 각각의 물건을 살 경우 드는 비용, 친구가 행복해할 정도, 그리고 물건을 반드시 사야 하는지를 규정하였다. 한 물건은 최대 한개만 살 수 있다. 동일한 물건을 여러번 사는 경우는 불가능하다.
1번 쿠폰의 경우 사려고 하는 물건 값의 합이 V1달러 이하의 선물들을 살 수 있다. 대부분의 쿠폰처럼 잔액이 남더라도 돌려 받지 못한다. 2번 쿠폰의 경우도 값이 V2인 것 빼곤 사용법이 동일하다. 두 쿠폰을 따로 사용하는 것은 가능하다. 허나 두 쿠폰의 액수를 합쳐 한 물건을 구매하는 것은 불가능하다.
그리고 이 백화점에선 생일인 사람의 선물을 사주려고 할 겨우, 물건 하나는 공짜로 살 수 있으며, 반드시 사야할 경우의 물건은 반드시 구매해야 한다. 물건들의 정보가 주어지고 쿠폰들의 액수가 주어졌을 때, 구매한 행복도의 합이 최대가 되는 조합을 찾는 프로그램을 작성하라.
Entrada
입력의 첫 번째 줄에는 V1, V2, N(1≤V1≤500, 1≤V2≤50, 1≤N≤300)이 입력된다.
그리고 N 개의 줄에는 선물에 대한 정보 P, H, S(1 ≤ P, H ≤ 1,000)이 입력된다. P는 물건의 가격을 뜻하고, H는 그 물건을 샀을 경우의 행복도를 뜻한다. S=1일 경우 반드시 사야하는 물건이고, S=0일 경우 반드시 살 필요가 없는 물건이다.
Salida
반드시 사야 하는 물건들을 구매하고, 그 외의 물건을 사거나 사지 않았을 때의 행복도의 최대를 출력하라.
만약에 반드시 사야 하는 물건들을 모두 사지 못할 경우에는 -1을 출력한다.
-1만 출력하는 경우는 0점으로 간주한다.
Ejemplo #1
3 2 4
3 10 1
2 10 0
5 100 0
5 80 0
120
Ejemplo #2
3 2 4
3 10 1
2 10 0
5 100 0
5 80 1
100
Debes iniciar sesión para escribir código.