RiseOJ – 로봇 소 떼

설명

베시는 진짜 같은 로봇 소 $$K$$ 마리( $1 \leq K \leq 100,000$ )로 소 떼를 만들어 농부 존을 속이려 하고 있다.

알고 보니 로봇 소를 만드는 일은 꽤 복잡하다. 로봇에는 마이크로컨트롤러를 연결해야 하는 위치가 $$N$$ 개( $1 \leq n \leq 100,000$ ) 있다(각 위치에 마이크로컨트롤러를 정확히 하나씩 연결해야 한다). 각 위치마다 베시는 가격이 서로 다른 여러 모델의 마이크로컨트롤러 중에서 하나를 고를 수 있다.

로봇 소 떼가 농부 존에게 그럴듯하게 보이려면, 어떤 두 로봇도 똑같이 행동해서는 안 된다. 따라서 어떤 두 로봇도 마이크로컨트롤러 구성이 완전히 같아서는 안 된다. 임의의 두 로봇에 대해, 두 로봇이 서로 다른 모델의 마이크로컨트롤러를 사용하는 위치가 적어도 하나 있어야 한다. 이 조건을 만족할 만큼 서로 다른 마이크로컨트롤러 모델이 항상 충분히 존재함이 보장된다.

베시는 로봇 소 떼를 최대한 저렴하게 만들고 싶다. 이를 위한 최소 비용을 구해 베시를 도와주자!

문제 출제: 리처드 펭(Richard Peng), 네이선 핀스커(Nathan Pinsker)

제약

문제 출제: 리처드 펭(Richard Peng), 네이선 핀스커(Nathan Pinsker)

입력 형식

입력의 첫째 줄에 $$N$$ 과 $$K$$ 가 공백으로 구분되어 주어진다.

다음 $$N$$ 개의 줄에는 각 위치에서 사용할 수 있는 서로 다른 마이크로컨트롤러 모델들에 대한 설명이 주어진다. 그중 $$i$$ 번째 줄은 위치 $$i$$ 에서 사용할 수 있는 모델의 수 $$M_i$$ ( $1 \leq M_i \leq 10$ )로 시작한다. 이어서 공백으로 구분된 $$M_i$$ 개의 정수 $P_{i,j}$ 가 주어지며, 이는 각 모델의 가격이다( $1 \le P_{i,j} \le 100,000,000$ ).

출력 형식

로봇 $$K$$ 대를 만드는 데 필요한 최소 비용을 한 줄에 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 roboherd.in · 출력을 쓸 파일 roboherd.out

예제 1

입력

3 10
4 1 5 3 10
3 2 3 3
5 1 3 4 6 6

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > December > Platinum

올림피아드 > USACO > 2016-2017 > December > Platinum

태그

JudgeUSACO

로봇 소 떼

평가 및 의견

풀이 제출