당신은 성의 주인이 되어 몰려오는 몬스터들을 물리쳐야 한다.
성은 길이 의 일차원 경로의 좌표 에 위치해 있다. 총 초 동안 매초 한 마리의 몬스터가 좌표 에서 소환된다. 이미 소환되어 있던 몬스터는 매초 좌표가 만큼 증가하는 방향으로 전진한다.
몬스터가 성에 도달하면 성은 공격을 받고, 그 몬스터는 소멸한다. 모든 몬스터의 체력은 이고, 당신의 공격력은 이다.
당신은 매초 살아 있는 몬스터 한 마리를 골라 의 데미지를 줄 수 있다. 공격을 받은 몬스터의 체력은 만큼 감소하고, 체력이 이하가 되면 해당 몬스터는 소멸한다.
몬스터가 소환되자마자 공격하는 것은 가능하다. 또한 몬스터가 좌표 으로 이동하는 순간 그 몬스터를 공격해 소멸시키면, 그 몬스터는 성을 공격하지 못한 것으로 판정한다.
더 이상 살아 있는 몬스터가 없을 때까지 공격할 수 있다. 즉, 마지막 몬스터가 소환된 이후에도 아직 살아 있는 몬스터가 있다면 계속 공격할 수 있다.
성을 최소한으로 공격받게 하기 위해 최대한 많은 몬스터를 잡고자 한다. 잡을 수 있는 몬스터 수의 최댓값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 잡을 수 있는 몬스터 수의 최댓값을 한 줄에 하나씩 출력한다.
첫 번째 테스트 케이스에서는 몬스터 한 마리를 즉시 잡을 수 있다.
두 번째 테스트 케이스에서는 각 몬스터를 잡기 위해 번 공격해야 하며, 두 몬스터를 모두 잡을 수 있다.
세 번째 테스트 케이스에서는 한 몬스터를 잡기 위해 번 공격해야 하지만, 어떤 몬스터도 성에 도달하기 전까지 번 공격할 수 없다.
