From: 2020-03-16 00:00:00 To: 2020-07-01 00:00:00 Now: 2024-11-23 18:29:39 Status: Public

Y - Working Dead (Challenge)

Time Limit: 1s Memory Limit: 128MB

Submissions: 1 Solved: 0

Description

대학원생 n명이 함께 일을 하려고 한다. 선행작업이 있는 경우, 모든 선행작업이 완료된 이후에 진행할 수 있다.

최대한 빨리 한다면 며칠만에 끝마칠 수 있을지 구해보자. 단, 이들은 대학원생이므로 휴일은 주어지지 않는다.

Input

* Line 1: 사람수 n이 입력된다. (1≤n≤10)

* Line 2: 작업의 갯수 N이 입력된다. (1≤N≤50)

* Line 3~N+2: 작업 0부터 작업 N-1까지 작업 소요날짜 d, 필요인원 p, 선행작업 갯수s와 번호 si가 입력된다. (1≤d≤10, 1≤p≤n, 0≤s≤N-1, 0≤si≤N-1)

Output

* Line 1 : 최소 소요기간을 출력한다.

Sample Input

3
6
1 1 0
2 1 1 3
2 1 0
1 1 0
1 2 3 0 1 2
4 1 0

Sample Output

Hint

1명이 4일간 작업 5를 하고, 나머지 2명이 작업 0~4를 진행하면 4일 안에 가능하다.

가능한 답은 여러 가지 있으며, 그 중 하나는 다음과 같다.

위상정렬을 공부해보자.