You are playing a game where you are in a train. The train consists of n cars, and you start the game in car x. On each turn you can move one car left or right or stay in your current car. The total duration of the game is t turns.

You know that during the game, a coin will appear to each car. For each car i, you know the value of the coin (v_i) and the turn when the coin appears (k_i). You can collect coin i if you move to car i (or stay in car i) on turn k_i or later.

What is the maximum total value you can collect?

Input

The first line contains three integers: n, t and x. Then n lines follow, and each line contains two integers, v_i and k_i.

Output

Output the maximum total value of the coins.

Constraints

• 1 \le n \le 100
• 1 \le t \le 500
• 1 \le x \le n
• 1 \le v_i \le 10^5
• 1 \le k_i \le t

Example

Input:

7 8 4
2 2
12 8
1 2
2 7
6 1
2 5
10 3

Output:

29