사다리 |
---|
여러 층으로 이루어진 직사각형 모양의 건물이 있다. 아래 그림 1은 5개의 층으로 이루어진 직사각형 건물의 예이다. 각 층에는 하나의 막대기가 있는데, 각 막대기의 길이는 서로 다를 수 있다. 그리고 막대기들은 시간 0에서 시작해서 동시에 왼쪽에서 오른쪽으로 혹은 오른쪽에서 왼쪽으로 움직인다. 시간은 정수시간 단위(0, 1, 2, ...)로 흐르고, 모든 막대기들은 단위시간당 길이 1만큼 움직인다. 아래 그림 1에서처럼 초기(시간 0)에 각 막대기는 직사각형의 왼쪽 변 또는 오른쪽 변에 닿아있다. 시간이 지남에 따라 각 막대기는 주어진 방향으로 움직이고 막대기의 양쪽 끝 중에 하나가 직사각형의 왼쪽 변 또는 오른쪽 변에 닿으면 진행하는 방향과 반대 방향으로 계속해서 움직인다. 철수(그림 1의 검정색 원)는 초기에 가장 아래층막대기 위에 위치하고 있다. 그리고 아래 조건 1)을 만족하면서 현재 막대기 위에서 움직일 수 있고, 조건 2)를 만족한다면, 하나 위층의 막대기로 올라 갈 수 있다. 조건 1) 현재 위치하고 있는 막대기 위에서는 0시간에 움직일 수 있다. (즉, 막대기 위에서의 움직임은 시간이 걸리지 않는다.) 조건 2) 철수가 현재 위치하고 있는 막대기의 임의의 위치에서 수직으로 이동 했을 때, 바로 위 층의 막대기 구간 안에 있으면(구간의 양쪽 끝 포함) 0시간에 바로 위 층의 막대기로 수직으로 올라갈 수 있다. (즉, 이 조건을 만족해서 하나 위층으로 올라 갈 수 있다면, 올라가는 움직임은 시간이 걸리지 않는다.) 예를 들어서, 아래 그림 2에서처럼 철수는 시간 2에 두 번째 층을 지나 세 번째 층의 막대기로 움직일 수 있다. 그리고 그림 3에서처럼 시간 4에 네 번째 층을 지나 다섯 번째 층의 막대기에 도달할 수 있다. 시간 0의 초기 상태에서 출발해서 철수가 가장 아래층의 막대기에서 가장 위층의 막대기로 올라가는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오. |
입력 | |
---|---|
첫 번째 줄에 층 수 N (1<=N<=3,000)과 층의 길이 L (1<=L<=3,000, L은 짝수)이 주어진다. 가장 아래층은 1층이고 가장 위층은 N층이다. 다음 N개의 줄 중 i번째 줄에는 i층의 막대기의 길이 l (1<=l<=L, l은 짝수)과 초기에 막대기가 움직이는 방향 d (d=0,1)가 주어진다. 여기서, d의 값 0은 왼쪽에서 오른쪽, 1은 오른쪽에서 왼쪽을 의미한다. 또한 초기에 막대기들은 방향이 0인 경우 층의 왼쪽 벽에, 1인 경우 층의 오른쪽 벽에 닿아 있다고 가정한다. |
출력 | |
---|---|
첫째 줄에 철수가 가장 아래층 막대기에서 가장 위층 막대기로 올라가는데 걸리는 최소 시간을 하나의 정수로 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 5 12 4 1 4 0 2 0 2 1 6 0 | |
출력 | 4 |