Syöte

Syötteen ensimmäinen rivi sisältää kokonaisluvut n ja m. Voit olettaa, että n \le 50 ja m \le 10000.

Tämän jälkeen syötteessä on n riviä, joista jokaisella on m kokonaislukua. Nämä rivit kuvaavat matriisin sisällön. Jokainen matriisin luku on välillä 0 \ldots 100.

Lopuksi syötteessä on n riviä, jotka kuvaavat välien rajat. Jokaisella rivillä on kaksi kokonaislukua a ja b (1 \le a \le b \le m).

Ratkaisun täytyy kulkea matriisin alariviltä yläriville. Voit olettaa, että jokin ratkaisu mahtuu matriisiin.

Tuloste

Ohjelmasi täytyy tulostaa paras ratkaisu.

Esimerkki

Syöte:

3 5
0 0 0 0 5
0 0 0 7 0
0 2 2 0 0
1 2
1 2
1 2

Tuloste:

4