수업을 듣다가 갑자기 신호가 온 당신은 화장실에 왔습니다. 화장실에는 n개의 두루마리 휴지가 걸려 있었습니다. 풀린 길이가 달라서 신경쓰인 당신은 모든 두루마리 휴지가 같은 길이로 풀려 있게 하고 싶어서 각 두루마리 휴지를 풀거나 되감아 모두 같은 길이로 만들려고 합니다.
당신은 한 번의 동작으로 하나의 두루마리 휴지를 선택하여 1cm 풀거나 1cm 되감을 수 있습니다. 물론 각 휴지의 남아있는 길이를 초과하여 풀 수는 없습니다. 가장 적은 수의 동작으로 모든 두루마리 휴지가 동일한 길이로 풀려 있게 만들어 봅시다.
입력
입력의 첫 번째 줄에는 두루마리 휴지의 개수를 나타내는 하나의 정수 n(1 ≤ n ≤ 106)가 주어집니다. 다음 줄부터 한 줄에 하나씩 i번째 두루마리 휴지에 대한 설명이 주어집니다. 두루마리 휴지에 대한 설명은 두 개의 정수 di 및 ri 형태로 나타납니다. di는 두루마리 휴지의 남아있는 길이, ri는 두루마리 휴지가 풀려있는 길이를 나타냅니다. (0 ≤ri ≤ di ≤ 109).
iktk 2년 전 1
문제
수업을 듣다가 갑자기 신호가 온 당신은 화장실에 왔습니다. 화장실에는 n개의 두루마리 휴지가 걸려 있었습니다. 풀린 길이가 달라서 신경쓰인 당신은 모든 두루마리 휴지가 같은 길이로 풀려 있게 하고 싶어서 각 두루마리 휴지를 풀거나 되감아 모두 같은 길이로 만들려고 합니다.
당신은 한 번의 동작으로 하나의 두루마리 휴지를 선택하여 1cm 풀거나 1cm 되감을 수 있습니다. 물론 각 휴지의 남아있는 길이를 초과하여 풀 수는 없습니다. 가장 적은 수의 동작으로 모든 두루마리 휴지가 동일한 길이로 풀려 있게 만들어 봅시다.
입력
입력의 첫 번째 줄에는 두루마리 휴지의 개수를 나타내는 하나의 정수 n(1 ≤ n ≤ 106)가 주어집니다. 다음 줄부터 한 줄에 하나씩 i번째 두루마리 휴지에 대한 설명이 주어집니다. 두루마리 휴지에 대한 설명은 두 개의 정수 di 및 ri 형태로 나타납니다. di는 두루마리 휴지의 남아있는 길이, ri는 두루마리 휴지가 풀려있는 길이를 나타냅니다. (0 ≤ri ≤ di ≤ 109).
출력
필요한 동작 수의 최솟값을 출력합니다.