사다리

여러 층으로 이루어진 직사각형 건물이 있다. 건물의 가로 길이는 모든 층에서 같고, 각 층에는 막대기 하나가 놓여 있다. 막대기의 길이는 층마다 다를 수 있다. 모든 막대기는 시간 0에 동시에 움직이기 시작하며, 단위 시간마다 길이 1만큼 왼쪽에서 오른쪽으로 또는 오른쪽에서 왼쪽으로 이동한다. 시간은 0, 1, 2, ...처럼 정수 단위로 흐른다.

시간 0에 각 막대기는 직사각형의 왼쪽 변 또는 오른쪽 변에 닿아 있다. 막대기는 주어진 방향으로 움직이다가 어느 한쪽 끝이 직사각형의 왼쪽 변 또는 오른쪽 변에 닿으면 즉시 방향을 바꾸어 계속 움직인다.

그림 1. 시간 0의 초기 상태

철수는 처음에 가장 아래층의 막대기 위에 있다. 철수는 다음 두 조건에 따라 움직일 수 있다.

조건 1) 현재 서 있는 막대기 위에서는 원하는 위치로 시간이 걸리지 않고 이동할 수 있다.

조건 2) 현재 막대기 위의 어떤 위치에서 수직으로 올라갔을 때 바로 위층 막대기의 구간 안에 도착한다면, 양 끝점을 포함하여 그 막대기로 시간이 걸리지 않고 올라갈 수 있다.

예를 들어 아래 그림 2에서는 시간 2에 두 번째 층을 지나 세 번째 층의 막대기로 올라갈 수 있다. 그림 3에서는 시간 4에 네 번째 층을 지나 다섯 번째 층의 막대기에 도달할 수 있다.

그림 2. 시간 2

그림 3. 시간 4

시간 0의 초기 상태에서 출발하여 철수가 가장 아래층 막대기에서 가장 위층 막대기로 올라가는 데 필요한 최소 시간을 구하라.

첫째 줄에 층 수 N과 층의 가로 길이 L이 주어진다. 가장 아래층은 1층, 가장 위층은 N층이다.

다음 N개의 줄 중 i번째 줄에는 i층 막대기의 길이 l과 초기 이동 방향 d가 주어진다. d = 0이면 막대기가 처음에 왼쪽 변에 닿아 있으며 오른쪽으로 움직이고, d = 1이면 처음에 오른쪽 변에 닿아 있으며 왼쪽으로 움직인다.

제한은 다음과 같다.

• 1 ≤ N ≤ 3,000
• 1 ≤ L ≤ 3,000, L은 짝수
• 1 ≤ l ≤ L, l은 짝수
• d는 0 또는 1

철수가 가장 아래층 막대기에서 가장 위층 막대기로 올라가는 데 필요한 최소 시간을 정수 하나로 출력한다.