Uolevi on käynyt nostamassa kalaverkot. Verkkoon on tarttunut saaliiksi sekä haukia että katkarapuja.

Voit myydä jokaisen verkkoon jääneen hauen 1 kultakolikon hinnalla. Kuitenkin jokaisesta verkkoon jääneestä katkaravusta joudut maksamaan 10 kultakolikkoa sakkoa.

Leikkaat verkkoon yhden kolmionmuotoisen reiän, jonka sisälle jäävää saalista ei lasketa myyntiin eikä sakkoon. Kuinka reikä kannattaa leikata, jotta saat suurimman mahdollisen määrän kultakolikoita?

Kalaverkko on n\times m kokoinen kuusikulmioista koostuva ruudukko. Annettuna on tieto saaliin sijainnista verkossa siten, että jokainen kuusikulmio verkossa on joko tyhjä, sisältää hauen tai sisältää katkaravun.

T-kokoinen kolmio ruudukossa koostuu T vierekkäisestä vaakatasossa olevasta ruudusta, sekä ylös- tai alaspäin osoittavasta T pituisesta kärjestä. Tätä on havainnollistettu kuvassa alla. Leikattava kolmio voi olla minkä tahansa positiivisen kokonaisluvun kokoinen, kunhan se on kokonaan verkon sisällä. Et voi jättää reikää leikkaamatta.

Kalaverkon koordinaatisto toimii seuraavan kuvan mukaisesti. Kuvaan on merkitty koordinaattiparit a,b, jotka merkitsevät kuusikulmioruudun riviä ja saraketta.

Seuraavassa kuvassa on värjätty oranssilla kolme mahdollista reikää, jotka voisit leikata. Yksi rei'istä on on kokoa T=1. Toinen reikä on kokoa T=2 ja sen kärki osoittaa ylöspäin. Kolmas reikä on kokoa T=3 ja sen kärki osoittaa alaspäin.

Syöte

Ensimmäisellä rivillä on kokonaisluvut n, m ja k: verkon korkeus, leveys ja saaliin määrä.

Seuraa k riviä muotoa a b c: rivillä a sarakkeella b sijaitsevassa kuusikulmiossa on saalis c. Saalis on joko merkki H eli hauki tai merkki K eli katkarapu.

Tuloste

Tulosta yksi kokonaisluku: suurin mahdollinen kultakolikoiden määrä jonka Uolevi voi saada saalistaan. Huomioi, että määrä saattaa olla negatiivinen.

Esimerkki

Syöte:

5 6 13
1 1 K
5 1 K
2 2 H
4 2 H
5 2 H
2 6 K
3 3 H
3 4 K
3 5 H
3 6 K
4 4 K
2 5 H
5 5 H

Tuloste:

-16

Selitys: Syötteen kalaverkko on havainnollistettu kuvassa. Leikkaamalla oranssilla merkityn alueen pois, ansaitset -16 kultakolikkoa jäljelle jäävistä 4 hauesta ja 2 katkaravusta.

Rajat

• 1 \leq a \leq n
• 1 \leq b \leq m
• 0 \leq k \leq nm

Osatehtävä 1 (37 pistettä)

• 1 \le n, m \le 10

Osatehtävä 2 (63 pistettä)

• 1 \le n, m \le 500