Uolevi pelaa peliä. Pelissä on n ruutua rivissä ja yhdellä vuorolla Uolevi voi siirtyä joko vasemmanpuoleiseen tai oikeanpuoleiseen ruutuun tai pysyä paikallaan. Uolevi aloittaa ruudusta x ja peli kestää t vuoroa.

Pelin aikana jokaiseen ruutuun ilmestyy kolikko. Jokaisesta ruudusta i tiedetään että siihen ilmestyvän kolikon arvo on v_i ja kolikko ilmestyy ruutuun vuorolla k_i. Kolikon voi kerätä liikkumalla ruutuun i (tai pysymällä ruudussa i) vuorolla k_i tai myöhemmin.

Mikä on suurin kolikkojen kokonaisarvo jonka voit kerätä pelin aikana?

Syöte

Syötteen ensimmäisellä rivillä on kolme lukua, n, t, x. Seuraavilla n:llä rivillä on jokaisella luvut v_i ja k_i.

Tuloste

Tulosta suurin kolikkojen kokonaisarvo.

Rajat

• 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

Esimerkki

Syöte:

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

Tuloste:

29