시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 1320 | 962 | 753 | 76.994% |
강호네 회사에는 직원이 N명이 있고, 해야 할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.
각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.
각각의 직원이 할 수 있는 일의 목록과 그 일을 할 때 강호가 지급해야 하는 월급이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지, 그리고 그 때 강호가 지불해야 하는 월급의 최댓값을 구하는 프로그램을 작성하시오.
첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 400)
둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호와 그 일을 할 때 지급해야 하는 월급이 주어진다. 월급은 10,000보다 작거나 같은 자연수 또는 0이다.
첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.
둘째 줄에는 강호가 지급해야 하는 월급의 최댓값을 출력한다.
5 5 2 1 3 2 2 1 1 5 2 2 1 3 7 3 3 9 4 9 5 9 1 1 0
4 23