BOJ 1658 돼지 잡기

문제 링크:

문제 내용

$M$개의 돼지우리에 $1, 2, \cdots, M$의 번호가 매겨져 있으며, $i$번 돼지우리에는 현재 $P_i$마리의 돼지가 있습니다.

$N$명의 손님이 순서대로 와서 다음과 같은 방식으로 돼지를 사 가려고 합니다.

• $i$번째 손님은 $K_{i1}, K_{i2}, \cdots, K_{iA_i}$번 돼지우리를 열고, 열린 돼지우리에서 최대 $B_i$마리의 돼지를 사 갑니다.
• 그 뒤에는 열린 돼지우리에 남아있는 돼지들을 원하는 대로 재분배한 뒤 돼지우리들을 모두 닫습니다.

이때 팔 수 있는 돼지의 수의 최댓값을 구하세요.

입력

첫 줄에는 돼지우리의 수 $M$과 손님의 수 $N$이 주어집니다. ($1 \le M \le 1000$, $1 \le N \le 100$)

두 번째 줄에는 각 돼지우리에 있는 돼지의 수 $P_i$가 순서대로 주어집니다. ($0 \le P_i \le 1000$)

다음 $N$줄에는 각각 $i$번째 손님의 행동을 나타내는 값 $A_i, K_{i1}, K_{i2}, \cdots, K_{iA}, B_i$가 주어집니다. ($0 \le A \le M$, $0 \le B \le 10^9$)

문제 풀이