lionix   2년 전

엔지니어 SKK는 K 로봇 청소기 (1 ≤ K≤100,000) 그룹을 구축하려고합니다.

로봇 청소기를 만드는 것은 꽤 복잡합니다. 마이크로 컨트롤러가 연결되어야하는 로봇에는 N (1≤N≤100,000) 개의
 개별 부품이 있습니다 (따라서 각 부품에 단일 마이크로 컨트롤러를 연결해야합니다). 이 각각의 부품에 대해 SKK는 
다양한 마이크로 컨트롤러 모델을 선택할 수 있습니다.

로봇 청소기 그룹이 정상적으로 작동하려면 모든 로봇이 동일해야합니다. 다시 말해, 두 대의 로봇이 똑같은 마이크로 컨트롤러
 세트를 가져서는 안됩니다. 모든 로봇 청소기 쌍에는 로봇 청소기가 다른 모델의 마이크로 컨트롤러를 사용하는 부분이 있어야합니다.
 이 제약 조건을 만족시키기에 항상 다른 마이크로 컨트롤러 모델이 충분하다고 가정합시다.

SKK는 가장 저렴한 가격으로 로봇 그룹을 만들고 싶어합니다. 그녀가 이것을 할 수있는 최소 비용을 결정하도록 합시다.

INPUT FORMAT (input.in):

첫 번째 줄 : N과 K는 공백으로 구분됩니다.

N 라인 다음 : 각 부품에 사용할 수있는 다양한 마이크로 컨트롤러 모델에 대한 설명.

i 번째 라인은 Mi (1≤Mi≤10)로 시작하여 파트 i에 사용할 수있는 모델 수를 나타냅니다. 
그 다음 Mi 공간으로 분리 된 정수 P(i,j)는 이들 다른 모델의 비용을 제공합니다
 (1≤P(i,j)≤100,000,000).

OUTPUT FORMAT (output.out):

k 로봇을 만들기위해 필요한 마이크로콘트롤러의 최소 전체 가격을 출력하세요.

SAMPLE INPUT:
3 10
4 1 5 3 10
3 2 3 3
5 1 3 4 6 6

SAMPLE OUTPUT:

61

-----------------------------------------------------------------------------------------------------------------------------

쉽게 설명 드리면
2번째 라인부터 N번째라인까지 각 라인마다 숫자를 하나씩 뽑아서 중복없는 K개의 숫자조합을 만든 다음 그 합이 최소가 되게하라는 문제인데
어떻게 접근하는것이 좋을까요?

댓글을 작성하려면 로그인해야 합니다.