문제
KOIBS 스타강사 택쌤이 인기가 많아지고 많아져도 너무 지나치게 많아져서
결국 한 나라의 임금이 되었다.
택쌤은 자신의 저녁 식사가 항상 N첩상이길 원한다.
예를 들어 5첩상이면, 5종류의 반찬이 상에 오른다는 뜻이다.
이해를 위해서 항상 [김치, 고기류, 튀김, 무침, 국] 이 상에 오른다고 생각해보자.
각 반찬 종류별로, Mi개의 선택지로 다시 나뉜다.
김치를 예로 들자면, 김치가 배추김치, 나박김치, 열무김치, 총각김치 등으로 나뉠 것이고,
고기류라면 쇠고기, 돼지고기, 닭고기 등으로 나뉘는 식이다.
택쌤은 자신의 식사가 항상 새롭고, 서로 다르기를 원한다.
두 식단은 하나라도 다른 선택지의 음식이 나오면 다른 식단이다.
택쌤에게 [배추김치, 쇠고기, 고구마튀김, 전어무침, 된장국] 과
[배추김치, 쇠고기, 고구마튀김, 전어무침, 미역국]은 (놀랍게도) 다른 식단이다.
택쌤의 궁중 요리사는 최대한 재정을 아껴서 K일 동안의 택쌤의 식단을 짜려고 한다.
각 음식들의 비용이 주어질 때, K일 동안의 택쌤의 식단을 짜는
총 비용의 최솟값을 출력하는 프로그램을 작성하라.
첫 줄에 N과 K가 공백을 사이에 두고 주어진다.
입력
첫 줄에 N과 K가 공백을 사이에 두고 주어진다.
다음 N줄에 걸쳐서 각 반찬 종류의 정보가 주어진다.
각 줄에 있어서 처음에 숫자는 선택지의 수인 Mi이며,
그 다음 Mi개의 수 Pij는 i번 반찬 종류의 j번째 선택지의 비용을 뜻한다.
출력
첫 줄에 K일 동안 택쌤의 식단을 짜는 최소비용을 출력한다.
<제약형식>
1≤N≤100,000 , 1≤K≤100,000, 1≤Mi≤10, 1≤Pij≤108, K일의 식단을 모두 다르게 짜는 것은 항상 가능함.
모든 입력값은 정수.
부분문제를 따로 명시하진 않지만 모든 데이터가 최대로 크진 않습니다.
예제 #1
3 3
3 1 2 3
3 2 3 4
3 3 4 5
20
최솟값은 [1,2,3] [1,3,3] [1,2,4]로 3일치 식단을 짜는 경우이다.
물론 이게 유일하게 최솟값을 내는 경우는 아니다.
예제 #2
3 10
4 1 5 3 10
3 2 3 3
5 1 3 4 6 6
61
로그인해야 코드를 작성할 수 있어요.