USACO 2016 December Platinum #3 (Problem Credit: Richard Peng/Nathan Pinsker)- 수라상 > 문제은행 : 정보올림피아드&알고리즘




4534 : 수라상

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
2 회   
시도횟수
17 회   

문제

KOIBS 스타강사 택쌤이 인기가 많아지고 많아져도 너무 지나치게
많아져서 결국 한 나라의 임금이 되었다
.

 

 

택쌤은 자신의 저녁 식사가 항상 N첩상이길 원한다.

 

예를 들어 5첩상이면, 5종류의 반찬이 상에 오른다는 뜻이다

이해를 위해서 항상 [김치, 고기류, 튀김, 무침, ] 이 상에 오른다고
생각해보자
.

 

 

각 반찬 종류별로, Mi개의 선택지로 다시 나뉜다

김치를
예로 들자면
, 김치가 배추김치, 나박김치, 열무김치, 총각김치 등으로 나뉠 것이고

고기류라면 쇠고기, 돼지고기, 닭고기
등으로 나뉘는 식이다
.

 

 

택쌤은 자신의 식사가 항상 새롭고, 서로 다르기를 원한다

두 식단은 하나라도 다른 선택지의 음식
나오면 다른 식단이다

택쌤에게 [배추김치, 쇠고기, 고구마튀김, 전어무침, 된장국] [배추김치, 쇠고기, 고구마튀김, 전어무침, 미역국](놀랍게도) 다른 식단이다.

 

 

택쌤의 궁중 요리사는 최대한 재정을 아껴서 K일 동안의
택쌤의 식단을 짜려고 한다

각 음식들의 비용이 주어질 때, K
동안의 택쌤의 식단을 짜는 총 비용의 최솟값을 출력하는 프로그램을 작성하라
. 

 


입력형식

첫 줄에 NK가 공백을 사이에 두고 주어진다.

다음 N줄에 걸쳐서 각 반찬 종류의 정보가 주어진다.

각 줄에 있어서 처음에 숫자는 선택지의 수인 Mi이며

그 다음 Mi개의 수 Pij i번 반찬 종류의 j번째 선택지의 비용을 뜻한다. 


출력형식

 첫 줄에 K일 동안 택쌤의 식단을 짜는 최소비용을 출력한다.

 


<제약형식>

1≤N≤​100,000 , 1≤​K≤​​100,000, 1≤​​​Mi≤​​10, 1≤​​​Pij≤​​​108, K일의 식단을 모두 다르게 짜는 것은 항상 가능함. 

모든 입력값은 정수.

부분문제를 따로 명시하진 않지만 모든 데이터가 최대로 크진 않습니다.


입력 예

3 3
3 1 2 3
3 2 3 4
3 3 4 5

출력 예

20

입력 예

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

출력 예

61

Hint!

입력 예시1의 경우, 최솟값은 [1,2,3] [1,3,3] [1,2,4] 3일치 식단을 짜는 경우이다. 물론 이게 유일하게 최솟값을 내는 경우는 아니다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP