N마리의 염소들은 정수 위치에 있는 말뚝에 밧줄로 묶여있다. 모든 염소는 자신이 최대한 동쪽으로 끌 수 있는 한 끈을 잡아 당기고 있다.

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

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

#8120 upload 41 done 18 how_to_reg 16 call_split Subtask

끈에 묶인 염소 timer 1s memory 512MB

#8120
Subtask

끈에 묶인 염소 1s 512MB