컨설팅 일거리

컴퓨터로 생성된 세계 Matriks에서, 당신은 멋진 사무실 공간에 독특한 미끄럼틀이 필요한 세련된 IT 회사들의 컨설턴트로 일한다. 지난 한 해 동안 당신은 서로 다른 시점에 여러 건의 일자리 제안을 받았으며, 시점은 연초부터 지난 시간을 밀리초 단위로 측정한다. 각 일자리에서는 회사를 위해 소형, 중형 또는 초대형 미끄럼틀을 설계할 수 있으며, 각각 $2 \cdot 10^5$, $3 \cdot 10^5$, $4 \cdot 10^5$밀리초가 걸리고, 제안을 수락하면 제안이 주어진 직후부터 작업을 시작한다. 한 의뢰를 수행하는 동안에는 그 시간에 제안되는 다른 모든 의뢰를 거절해야 한다. 한 해를 돌이켜 보면 특별히 불만스럽지는 않지만(미끄럼틀을 설계하는 일에 누가 불평하겠는가?), 어쩌면 어떤 일자리 제안을 수락할지 다르게 선택하여 더 많이 벌 수도 있었을 것이다. 당신은 일한 시간 $10^5$밀리초당 고객에게 쿠키 $1$개를 청구한다. 수락할 의뢰와 각 의뢰의 길이를 최적으로 선택했다면 쿠키를 얼마나 벌 수 있었는가?

첫째 줄에 한 해 동안 받은 일자리 제안의 수를 나타내는 정수 $N$ ($1 \le N \le 10^5$)이 주어진다.

둘째 줄이자 마지막 줄에는 연초부터 밀리초 단위로 측정한 일자리 제안을 받은 시각을 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다. 한 해는 $31\,556\,926 \cdot 10^3$밀리초로 이루어진다. 각 일자리 제안은 한 해가 끝나기 적어도 $4 \cdot 10^5$밀리초 전에 주어졌음이 보장된다.

벌 수 있었던 쿠키의 최대 개수를 정수로 출력한다.

가능한 해법 하나는 첫 번째, 세 번째, 네 번째 일자리를 맡아 각각 초대형 미끄럼틀을 만드는 것이다. 그 결과 쿠키 $12$개를 얻는다. 일자리 제안 사이의 시간은 적어도 $4 \cdot 10^5$밀리초이므로 어떤 의뢰도 겹치지 않는다.