1부터 N까지 번호가 매겨진 N N$N$ 종류의 책을 M 개의 인터넷 서점에서 구입해야 합니다. 각 책은 적어도 하나의 서점에서 구입할 수 있으며 (즉, 항상 N 종류의 책을 구입할 수 있습니다) 여러 서점에서 파는 경우 서점마다 가격이 다를 수 있습니다. 또한 주문양과 관계없이 각 서점에서 주문하는 데 일정 금액의 운송료가 듭니다. 각 서점의 운송료와 책의 가격이 주어졌을 때, N 가지 종류의 책을 모두 구입하기 위한 최소 금액을 출력하세요.
[입력]
첫번째 줄에 사야하는 책의 가짓수 N (1 이상 100 이하) 과 서점의 수 M (1 이상 15 이하)이 공백으로 구분되어 주어집니다. 이후 M 개의 서점 정보가 차례대로 주어집니다. 각 서점의 정보는,
첫 번째 줄에 해당 서점에서 구입할 수 있는 책의 가짓수 K와 운송료가 공백으로 구분되어 주어집니다.
이 후 K개의 줄에 구입할 수 있는 책의 번호와 가격이 공백으로 구분되어 주어집니다.
[출력]
N 종류의 책을 모두 구입하기 위한 최소 금액을 출력합니다.
[제한]
모든 입력값은 정수입니다. 책 한 권 가격과 운송료는 모두 10,000을 초과하지 않습니다. 책의 가격은 항상 자연수이고, 일부 서점은 운송료가 0원일 수 있습니다.
[추가 설명]
(해당 부분은 문제에 써있지 않지만, 문제 이해를 돕기 위해 제가 임의로 작성하였습니다.)
테스트 케이스는 7 종류의 책을 4개의 서점에서 최소 금액으로 구매해야 하는 상황입니다.
1번 서점에서는 4 종류의 책을 구매할 수 있으며, 주문할 경우 9원의 운송료를 지불해야 합니다. 1번 서점에서는 1번 책을 28원에, 6번 책을 45원에, 3번 책을 49원에, 4번 책을 108원에 구매할 수 있습니다.
2번 서점에서는 7 종류의 책을 구매할 수 있으며, 주문할 경우 49원의 운송료를 지불해야 합니다.
3번 서점에서는 5 종류의 책을 구매할 수 있으며, 주문할 경우 20원의 운송료를 지불해야 합니다.
4번 서점에서는 1 종류의 책을 구매할 수 있으며, 주문할 경우 0원의 운송료를 지불해야 합니다.
1번 서점에서 9원의 운송료와 1번, 3번, 4번 책을 구매하여 9 + 28 + 49 + 108 = 194원을, 3번 서점에서 20원의 운송료와 2번, 5번, 6번, 7번 책을 구매하여 20 + 184 + 133 + 42 + 249 = 628을 지불하여 194 + 628 = 822원에 모든 종류의 책을 구매할 수 있으며, 이보다 작은 경우는 없습니다.
bomul1128 3년 전 3
[문제]
1부터 N까지 번호가 매겨진 N N$N$ 종류의 책을 M 개의 인터넷 서점에서 구입해야 합니다. 각 책은 적어도 하나의 서점에서 구입할 수 있으며 (즉, 항상 N 종류의 책을 구입할 수 있습니다) 여러 서점에서 파는 경우 서점마다 가격이 다를 수 있습니다. 또한 주문양과 관계없이 각 서점에서 주문하는 데 일정 금액의 운송료가 듭니다. 각 서점의 운송료와 책의 가격이 주어졌을 때, N 가지 종류의 책을 모두 구입하기 위한 최소 금액을 출력하세요.
[입력]
첫번째 줄에 사야하는 책의 가짓수 N (1 이상 100 이하) 과 서점의 수 M (1 이상 15 이하)이 공백으로 구분되어 주어집니다. 이후 M 개의 서점 정보가 차례대로 주어집니다. 각 서점의 정보는,
[출력]
N 종류의 책을 모두 구입하기 위한 최소 금액을 출력합니다.
[제한]
모든 입력값은 정수입니다. 책 한 권 가격과 운송료는 모두 10,000을 초과하지 않습니다. 책의 가격은 항상 자연수이고, 일부 서점은 운송료가 0원일 수 있습니다.
[추가 설명]
(해당 부분은 문제에 써있지 않지만, 문제 이해를 돕기 위해 제가 임의로 작성하였습니다.)
테스트 케이스는 7 종류의 책을 4개의 서점에서 최소 금액으로 구매해야 하는 상황입니다.
1번 서점에서 9원의 운송료와 1번, 3번, 4번 책을 구매하여 9 + 28 + 49 + 108 = 194원을, 3번 서점에서 20원의 운송료와 2번, 5번, 6번, 7번 책을 구매하여 20 + 184 + 133 + 42 + 249 = 628을 지불하여 194 + 628 = 822원에 모든 종류의 책을 구매할 수 있으며, 이보다 작은 경우는 없습니다.