정올 국가에는 두 개의 마을이 있으며 각각 1, 2로 번호가 매겨져 있습니다.

이 마을에서는 총 N개의 이벤트가 발생합니다. 이 이벤트에는 1에서 N까지 번호가 붙습니다.

이벤트 i (1 \le i \le N)는 마을 P_i에서 개최되며 개최 시간은 S_i+0.1부터 S_i+0.9까지 입니다. 여기서 S_i는 정수입니다.

이벤트 i에 참가하기 위해서는 시간 S_i+0.1부터 S_i+0.9까지 마을 P_i에 있어야 합니다.

정올이는 이벤트 순회를 하기로 했습니다. 이벤트 순회에서는 여러 이벤트에 참가하고 필요하다면 마을과 마을 사이를 이동할 수도 있습니다.

정올이는 시간 0부터 이벤트 순회를 시작합니다. 이 때 원하는 마을에서 시작할 수 있습니다.

정올이는 마을 1과 마을 2 사이를 왔다 갔다 이동할 수 있습니다. 두 마을 사이를 이동하는 데 걸리는 시간은 정올이가 이동을 시작할 때까지 참여한 이벤트의 수를 j라고 했을 때, D + K*j입니다.

이벤트와 마을 간의 이동에 관한 정보가 주어집니다. 당신은 정올이가 참가할 수 있는 최대 이벤트 수를 출력하는 프로그램을 작성해야 합니다.

이벤트 순회 timer 2s memory 1024MB

이벤트 순회 2s 1024MB