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