자세히 보아야 예쁘다

시간 제한1초메모리 제한1024 MB

요약
각 친구를 A_i시간 이상 연속으로 보지 않으면서 M시간을 N명에게 나누어 줄 수 있는지 판정한다.
난이도

보통10점 중 4점

유형
그리디, 수학
정답자
아직 제출이 없습니다

문제

자세히 보아야 예쁘다. 오래 보아야 사랑스럽다.

- 나태주

위 글귀를 인상 깊게 보던 재원이는 한 가지 생각이 들었다. '가만... 디미고에서 사랑에 빠지면 나는 퇴학 처분을 받고 말 거야...!' 따라서 재원이는 한 친구를 너무 오랫동안 보지 않기로 했다.

재원이는 11번부터 NN번까지의 번호를 가진 NN명의 친구들과 디미고에서 MM시간 동안 생활하게 된다. 재원이는 항상 한 명 이상의 친구를 보아야 하며 11시간마다 그가 보는 친구를 바꿀 수 있다. 만약 ii번 친구를 A_iA\_i시간 이상 보게 된다면 사랑에 빠져 퇴학 처분을 받게 된다. 재원이가 사랑에 빠져 퇴학당하지 않도록 도와주자!

입력

첫 번째 줄에 두 정수 NN, MM이 공백으로 구분하여 주어진다.(1≤N≤105;1≤M≤1012)(1 \leq N \leq 10^5; 1 \leq M \leq 10^{12})

두 번째 줄에 정수 A_1,A_2,⋯ ,A_NA\_1, A\_2, \cdots, A\_N이 공백으로 구분하여 주어진다. (1≤A_1,A_2,⋯ ,A_N≤1012)(1 \leq A\_1, A\_2, \cdots, A\_N \leq 10^{12})

출력

첫 번째 줄에 재원이가 퇴학 처분을 받지 않을 수 있다면 DIMI를, 아니면 OUT을 출력한다.

힌트

디미고 교칙은 불건전한 이성교제에 엄격하다.

예제2

  1. 예제 1

    입력
    3 7
    3 3 3
    
    예상 출력
    OUT
    
  2. 예제 2

    입력
    3 6
    3 3 3
    
    예상 출력
    DIMI