题目描述

有 n 个任务，每个任务有处理时间 t[i] 和截止时间 d[i]。任务一旦开始不能中断，求最小最大延迟。 延迟定义为：任务的完成时间减去截止时间。最大延迟为所有任务延迟的最大值。 求一种任务执行顺序，使得最大延迟最小，输出这个最小的最大延迟值。

输入格式

第一行一个整数 n (1 <= n <= 50) 接下来 n 行，每行两个整数 t_i 和 d_i (1 <= t_i <= 10^4, 1 <= d_i <= 10^6)

输出格式

一个整数，表示最小可能的最大延迟。如果所有任务都能在截止时间前完成，最大延迟可能为负数，输出该负数。

样例

输入： 3 3 5 2 4 1 3 输出： 1

数据范围

1 <= n <= 50 1 <= t_i <= 10^4 1 <= d_i <= 10^6