pyy have some bonus to hand out. However, he is so parsimonious that he doesn't want to hand out too many bonus, so he wants the maximum bonus a person get can be as small as possible.

Finally he came up with an idea:

He stands at first, and write a number on each hand.

Others line up behind pyy, and write a number on each hand too.

The bonus everyone receives equals to the sum of the numbers on the right hands of all people standing in front of him(including pyy) minus the number on his own left hand. 

We have multiply cases. For each case:

The first line contains 3 numbers:

  N: the number of people who will get bonus(besides pyy)

  L: the number on pyy's left hand

  R: the number on pyy's right hand 

From second to N+1 lines, each line contains 2 numbers:

  Li: the number on the left hand of ith person

  Ri: the number on the right hand of ith person

0 < N <= 100000, 0 <= L, R, Li, Ri < 32768

The smallest maximum bonus.

2 5 2
4 3
1 6

4