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