문제
XYZ국의 모바일 네트워크 시장은 2개의 대기업 XYZ 텔레콤과, XYZ 모바일이 장악하고 있다.
XYZ국의 현재 사용하고 있는 주파수 대역이 포화 상태에 치달음에 따라,
특히 위의 두기업간의 주파수 대역 선점 싸움이 치열해 졌다.
주파수 대역은 총 30,000개의 채널로 나뉘어져 있으며, 이를 사용하기 위해서는 정부의 허가를 받아야 한다.
기업이 제공하는 서비스는 하나의 채널로만 이뤄지는 서비스가 있을 수 있으나,
여러 개의 채널을 사용한 서비스도 가능하며, 한 채널은 하나의 서비스를 위해서만 사용이 가능하다.
이 두 기업이 새로이 경매를 통해서 사용하는 주파수를 가져가고자 한다.
XYZ국의 중앙 정부는 경매에서 최대한의 이득을 얻고자 한다.
위의 두 기업이 서비스를 위해 입찰한 주파수의 경매 내역이 주어졌을 때,
XYZ국이 최대한 얼마의 이득을 얻을 수 있는지 알아보는 프로그램을 작성하라.
입력
입력은 두개의 기업의 경매내역이 주어진다.
첫 번째는 XYZ 텔레콤이 개시 하고자 하는 서비스의 개수 N(1<=N<=300)이 주어지며, N개의 경매내역이 주어진다.
각 경매 내역은 한 줄로 주어지는데 첫 번째는 경매를 위한 비용 P(1<=P<=1,000)이 주어지고, 그 다음에는 서비스에서 사용하고자 하는 채널의 수 X(1<=X<=32)가 주어진다. 그 다음에는 X개의 서비스를 위해 신청하고자 하는 채널의 번호가 주어진다. 채널의 번호는 1부터 30,000 이하의 번호가 매겨져 있다. 서비스를 위해 신청한 채널 번호는 하나의 서비스 내에서 겹쳐서는 안되며, XYZ 텔레콤이 신청한 모든 서비스에서 반드시 하나만 나와야 한다.
XYZ 텔레콤의 경매내역이 주어진 다음에는 XYZ 모바일이 개시하고자 하는 서비스의 개수 M(1<=M<=300)이 주어지며, 나머지는 XYZ 텔레콤의 경매내역에 대한 형식과 동일하다.
출력
경매내역에 대해서 입찰된 서비스를 채널이 겹치지 않게 선정했을 때 얻을 수 있는 최대이윤(중앙정부에서 선정한 서비스의 입찰 비용의합)을 출력한다.
예제 #1
3
45 1 1
51 1 2
62 1 3
4
54 1 1
15 1 2
33 1 3
2 2 4 5
169
예제 #2
5
20 1 1
18 1 2
23 1 4
54 3 3 5 6
17 1 7
4
36 3 1 2 3
28 1 5
47 2 4 7
16 1 6
139
로그인해야 코드를 작성할 수 있어요.