Годината е 2040. Новиот главен град на Македонија е всушност модерен град кој е претставен како мапа од полиња со r редови и k колони, низ која движењето е исклучиво кон исток, запад, север или југ. На мапата, улиците се претставени со ‘O’, зградите со ‘#’, и метро станиците со ‘M’. Оддалеченоста меѓу две соседни полиња е еден метар.
Домот на градоначалникот Тео (почетната точка) е означен со ‘T’, а неговата канцеларија (крајната цел) со ‘K’. На пример, една можна мапа (со 5 редови и 9 колони) би изгледала вака:

O##OOO#OO
TOOOOOOOO
OOM#OOMOO
OO#OMOOOO
OOOOOOKOO

Метро станиците се уште не постојат, па Тео сака анализа дали и каде треба да се постават. За различни мапи Тео го интересира колку би трошел при движење во градот од неговиот дом до неговата канцеларија.

Има 3 начини на патување кои може да се комбинираат: пешки, со изнајмен велосипед или со метро.
Одењето пешки е бесплатно, меѓутоа споро - на Тео му требаат 5 секунди да изоди 1 метар. Исто така, не може да оди низ полињата каде има зграда (‘#’).

Изнајмен велосипед може да се подигне и остави на кое било поле, и може да измине 1 метар во 2 секунди, но не може да се движи по полињата каде има зграда. Цената е 1 денар по метар.

Метро станиците ќе бидат поставени под земја (и затоа преку тие полиња не е проблем да се минува пешки или со велосипед). Сите метро станици се поврзани една со друга, но линиите се секогаш хоризонтални или вертикални (т.е. движењето е исто така само кон исток, запад, север или југ), и растојанието од една до друга станица е најкраткото можно. Метрото се движи со брзина од 1 метар во 1 секунда, и може да се движи под кое било поле, вклучувајќи и згради (‘#”). Метрото чини 5 денари по метар.

Конкретно, Тео го интересира која е најмалата сума на пари што ќе ја потроши за да стигне до канцеларијата од неговиот дом во максимум t секунди, доколку тоа е воопшто можно. Направете програма која тоа ќе го пресмета.

Влез

Во првиот ред се дадени бројот на редови r (1 ≤ r ≤ 50), бројот на колони k (1 ≤ k ≤ 50), бројот на метро станици m (0 ≤ m ≤ 100) и максималното дозволено време t (1 ≤ t ≤ 500).

Во следните r редови се дадени по k знаци A_ij, кои ќе ја имаат една од следниве вредности: ‘O’ доколку на позицијата (i,j) има само улица, ‘#’ доколку на позицијата има зграда, ‘M’ доколку има метро станица, ‘T’ доколку е почетната точка и ‘K’ доколку е крајната точка. Секогаш има само една почетна и само една крајна точка.

Забелешка.
За 25% од поените, ќе важи: t = 500, r ≤ 10, k ≤ 10 и m = 0.
За други 5% од поените, ќе важи: m = 0.
За други 10% од поените, ќе важи: m = 2.

Излез

Во првиот и единствен ред отпечатете ја најмалата сума на пари што Тео мора да ја потроши за да стигне до неговата канцеларија во максимум t време. Доколку тоа не е можно, отпечатете -1.

Ограничувања

Временско ограничување: 500 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
5 9 3 14	
O##OOO#OO
TOOOOOOOO
OOM#OOMOO
OO#OMOOOO
OOOOOOKOO

излез
25

влез
5 5 2 15
TM###
#####
#####
#####
###MK

излез
31

Објаснување за примерот: за да стигне до својата канцеларија во 14 секунди, Тео мора да земе велосипед до неговата најблиска станица (во 3-тиот ред и 3-тата колона, почнувајќи од горниот лев агол и броејќи од еден), па да се качи на метро до станицата која е најблиска до неговата канцеларија (3-тиот ред и 7-мата колона) и од таму повторно целиот пат да го помине со велосипед. Вкупно, има изминато 5 метри со велосипед (10 секунди и 5 денари) и 4 метри со метро (4 секунди и 20 денари).