Choosing Orders and Renting Machines

프로그램 명: ceoi_order

제한시간: 1 초

목수 Sam은 N개의 주문을 받습니다. 어느날 그녀는 주문을 받기 위해선 M개의 기계가 부족한 것을 알았습니다.

모든 주문이 부족한 기계가 모두 필요한 것은 아니지만 각 주문마다 적어도 하나의 기계가 더 필요합니다.

주문을 받기위해 Sam은 부족한 기계를 사거나 빌려야 합니다.

각각의 주문이 서로 다른 작업의 양과 시간을 필요로 하기 때문에 기계를 빌리는 비용은 어떻게 주문이 들어오느냐에 따라 다릅니다.

기계의 구입비용은 주문에 상관없이 일정합니다. 한번 산 기계는 다음번에 추가 비용없이 사용할 수 있습니다.

그녀는 주문을 받기에 추가적으로 기계를 사거나 빌리는 비용이 너무 비싸면 주문을 거절할 수 있습니다.(이 경우 이익,손실이 없습니다.)

Sam의 이익을 최대화 하기 위해서 어떤 주문을 거절할지, 어떤 기계를 사야할지, 그리고 어떤 기계를 빌려야할지 도와주세요

입력

첫째줄에는 N과 M을 입력합니다. N은 주문의 양, M은 필요한 머신의 개수입니다.
둘째줄부터는 주문과 기계의 상세정보를 입력합니다.
각각의 N은 다음과 같은 성분을 같습니다.
- vi(1 <= vi <= 5 000) 해당 주문을 완료했을때 얻는 소득
- mi(1 <= mi <= M) 해당 주문을 완료하기 위한 필요한 머신의 개수
각 N당 mi개의 기계는 다음과 같은 정보를 갖습니다.
- j (1 <= j <= M) : 해당 주문을 완료하기 위한 머신의 번호
- rij (1 <= rij <= 20 000) : 이 머신을 빌리는데 필요한 비용

예를들어 머신의 개수가 3개가 필요하면 각 머신의 번호는 무엇이고 빌리는 비용이 무엇인지 따로 써야 됩니다.

si (1 <= si <= 20 000): 번호별 머신의 구입비용(머신이 총 M개필요하면 M개를 씀)

출력

최대 이익값 출력

입출력 예(상세설명. 입력값 작성시 중간에 줄간격은 무시하세요)

입력 

2 3 (주문 2개를 받았고 총 3개의 머신이 부족합니다.) 

100 2 (첫번째 주문 완료시 100의 소득을 얻고 2개의 머신이 필요합니다.) 
1 30 (1번 머신이 필요하고 빌리는데 필요한 돈은 30입니다.) 
2 20 (2번 머신이 필요하고 빌리는데 필요한 돈은 20입니다.) 

100 2(두번째 주문 완료시 100의 소득을 얻고 2개의 머신이 필요합니다.) 
1 40(1번 머신이 필요하고 빌리는데 필요한 돈은 40입니다.) 
3 80(3번 머신이 필요하고 빌리는데 필요한 돈은 80입니다.) 

50(1번 머신의 가격) 
80(2번 머신의 가격) 
110(3번 머신의 가격) 

출력 

50(최대 이익)

출처:ceoi/2008/ 
번역:ironamor

출력값 해석

위의 입력값에서 이익을 최대화(50) 하기위해선 두가지 해법이 있습니다.

02번 주문을 거절, 01번을 완료, M1과 M2를 빌림
01과 02를 완료하고 M1을 구입, M2와 M3를 빌림

Carpenter Sam receives N orders. While reading the orders she realizes that she is missing M machines necessary to complete the orders. Not all orders require all missing machines, but every order requires at least one of them.

To complete an order, Sam needs to either buy or rent each of the machines the order requires. Since different orders need different amounts of work (and thus time) on each machine, the rent for a machine may depend on the order that is completed on it. The purchase cost for a machine do not depend on the orders, though. A machine which is purchased once can be used to work on any number of orders at no extra cost.

If the cost caused by an order seem too high to Sam, she may choose to reject an order; this will lead to no cost (and no profit).

Help Sam decide which orders to reject, which machines to buy, and which machines to rent in order to maximize her profit.

There are two solutions leading to the maximum profit of 50:

Reject O2, complete O1, rent both M1 and M2.
Complete both O1 and O2, buy M1, rent M2 and M3.

입력

The first line of the input contains two integers, N (1 <= N <= 1 200) and M (1 <= M <= 1 200). The following N blocks of lines each describe an order; they are structured as follows: The first line of block i contains two integers, the income value vi (1 <= vi <= 5 000) for order Oi and the number of machines mi (1 <= mi <= M) needed for Oi. The following mi lines each specify a machine j (1 <= j <= M) needed to complete Oi and the rent rij (1 <= rij <= 20 000) needed to rent this machine for this order.

The M lines after the last order block contain one integer each: the purchase price si (1 <= si <= 20 000) for each machine.

출력

The output contains exactly one integer: the maximum achievable profit.

입출력 예

출처:ceoi/2008/

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]