Hide

Problem I
Bruni Íslenskra Fræða

Languages en is

Atli has finally gone off the deep end. After being made to read yet another Icelandic Saga something broke and he’s going berserk in Hús Íslenskra Fræða. He’s decided to host a book burning and is trying to burn as many of the manuscripts and books in the building as possible. He’s started a fire that will last $t$ seconds. To keep the fire going for longer he’s running around collecting written works and tossing them into the fire. Being a programmer himself, he’s already calculated the optimal route despite having gone raving mad. Your job is to figure out how long his fire will last so the university knows how long they have to catch him red-handed.

Input

The input starts with a line with two integers $1 \leq n, t \leq 10^3$ where $n$ is the number of written works Atli can grab and $t$ is the lifetime of the fire in seconds. Next there are $n$ lines, each with two integers $1 \leq t_ i, f_ i \leq 10^3$. This denotes one of the written works Atli can grab. It takes Atli $t_ i$ seconds to fetch it and once it’s tossed on the fire it extends its lifetime by $f_ i$ seconds. For this to work the fire has to still be going when Atli returns after $t_ i$ seconds. If the flame dies the exact moment he returns he can use the hot ashes to keep things going.

Output

Print the number of seconds Atli can keep the fire going.

Sample Input 1 Sample Output 1
3 10
10 20
15 5
12 6
36