N마리의 염소들은 정수 위치에 있는 말뚝에 밧줄로 묶여있다. 모든 말뚝은 동서 방향으로 5,000,000미터에 달하는 길이의 울타리 내부에 있다. 모든 염소는 자신이 최대한 동쪽으로 끌 수 있는 한 끈을 잡아 당기고 있다 (단, 울타리의 끝을 넘어서지는 못한다).

다행히도, 염소들은 자유를 얻을 기회가 생겼다. 야생 염소가 지나가다가 그들을 발견한 것이다! 야생 염소는 날카로운 앞니를 가지고 있기에 남북 방향으로 빠르게 달려 서쪽에서부터 거리에 위치해 있는 밧줄을 모두 끊어버릴 수 있다. 단, 야생 염소의 체력에는 한계가 있기에 최소한의 횟수로 질주하고 싶다. 야생 염소가 질주하며 밧줄을 자르는 위치는 연속한 두 정수 좌표 사이의 중간에 위치하는 것이 가능하며, 해당 위치에 존재하는 모든 밧줄을 자르는 것이 가능하다.

각 밧줄의 길이와 그 말뚝의 위치가 주어질 때, 모든 염소들을 밧줄로부터 자유롭게 하려면 야생 염소가 최소한 몇 번의 자르기를 해야 하는지 구하는 프로그램을 작성하시오.

#8120 upload 1회 done 1회 how_to_reg 1명 call_split 서브태스크

끈에 묶인 소 timer 1초 memory 512MB

#8120
서브태스크

끈에 묶인 소 1초 512MB