전시장 (고등) timer 1s memory 128MB

T개의 그림을 전시할 수 있는 전시장이 있다.

전시장은 정기적으로 운영을 하는데 전시가 시작되면 D일 동안 운영을 한다.

이 전시장은 사용자가 그림을 가지고 와서 전시를 요청하면 전시할 수 있는 공간이 있을 경우 접수를 받는다.

전시공간은 T개가 있는데 1번부터 T번까지 번호가 매겨져 있으며 전시요청이 오면 전시요청 날짜가 가장 빠른 것을 1번으로 하여 순서대로 전시를 하게 되며 T번 다음에는 다시 1번에 전시한다.

요청 날짜가 같을 경우에는 먼저 요청한 것을 먼저 전시하게 된다.

일단 전시를 시작하면 3일 동안 전시를 하게 되는데 3일 이후에 해당 공간에 전시할 그림이 없으면 새로운 그림이 전시되기 전까지 계속 전시를 한다.

현재까지 전시 요청이 들어온 그림이 M개가 있다.

전시가 불가능한 요청은 받지 않기 때문에 이 그림들은 모두 전시가 가능하다.

진흥이는 자신의 그림을 전시하고 싶은데 가능하면 오랫동안 전시하기를 원한다.

진흥이가 전시를 요청하고 나면 더 이상 전시요청이 없다고 가정할 때 가장 오랫동안 전시하기 위해 전시 요청 날짜를 며칠로 하면 되는지 구하는 프로그램을 작성하라.

<부분문제의 제약 조건>

부분문제 1 : 전체 데이터의 10%는 T가 1이다.

부분문제 2 : 전체 데이터의 20%는 T와 M의 크기가 같다.

부분문제 3 : 전체 데이터의 70%는 원래의 제약조건 이외에 아무 제약조건이 없다.