#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int inf = 0x7ffffff;

int n, m, k, top, sx, sy, tx, ty, a[][], speed[], f[][][], dx[] = { , -, ,  }, dy[] = { , , , - },flag[];

char name[][],s[][];

struct node

{

    int x, y, zhuangtai;

};

int jisuan(int stu)

{

    int tot = ,sped = k;

    memset(flag, , sizeof(flag));

    while (stu)

    {

        tot++;

        flag[tot] = stu % ;

        stu /= ;

    }

    for (int i = ; i <= top; i++)

        if (flag[i] == )

            sped += speed[i];

    if (sped < )

        sped = ;

    return sped;

}

bool judge(int x, int y)

{

    if (x >=  && x <= n && y >=  && y <= m)

        return true;

    return false;

}

int bei(int stu, int x, int y)

{

    int cur, tot = ;

    for (int i = ; i <= top; i++)

        if (s[x][y] == name[i][])

        {

            cur = i;

            break;

        }

    memset(flag, , sizeof(flag));

    while (stu)

    {

        tot++;

        flag[tot] = stu % ;

        stu /= ;

    }

    if (flag[cur])

        return ;

    flag[cur] = ;

    for (int i = top; i >= ; i--)

        stu = stu *  + flag[i];

    return stu;

}

int fang1(int stu, int x, int y)

{

    memset(flag, , sizeof(flag));

    int tot = ;

    while (stu)

    {

        tot++;

        flag[tot] = stu % ;

        stu /= ;

    }

    for (int i = ; i <= top; i++)

        if (flag[i] == )

            flag[i] = ;

    for (int i = top; i >= ; i--)

        stu = stu *  + flag[i];

    return stu;

}

int fang2(int stu, int x, int y)

{

    int tot = ;

    memset(flag, , sizeof(flag));

    while (stu)

    {

        tot++;

        flag[tot] = stu % ;

        stu /= ;

    }

    for (int i = ; i <= top; i++)

        if (flag[i] ==  && speed[i] > )

            flag[i] = ;

    for (int i = top; i >= ; i--)

        stu = stu *  + flag[i];

    return stu;

}

int qpow(int a, int b)

{

    int res = ;

    while (b)

    {

        if (b & )

            res *= a;

        a *= a;

        b >>= ;

    }

    return res;

}

void bfs()

{

    queue <node> q;

    node temp;

    temp.x = sx;

    temp.y = sy;

    temp.zhuangtai = ;

    q.push(temp);

    while (!q.empty())

    {

        node u = q.front();

        q.pop();

        int sudu = jisuan(u.zhuangtai),x = u.x,y = u.y;

        //printf("%d %d %d\n", sudu, x, y);

        for (int i = ; i < ; i++)

        {

            int nx = x + dx[i], ny = y + dy[i];

            if (judge(nx, ny))

            {

                //只移动

                if (s[nx][ny] != '#' && f[u.zhuangtai][nx][ny] > f[u.zhuangtai][x][y] + sudu)

                {

                    f[u.zhuangtai][nx][ny] = f[u.zhuangtai][x][y] + sudu;

                    node temp;

                    temp.x = nx;

                    temp.y = ny;

                    temp.zhuangtai = u.zhuangtai;

                    q.push(temp);

                }

                //背人

                if (s[nx][ny] >= 'A' && s[nx][ny] <= 'Z')

                {

                    int stu = bei(u.zhuangtai, nx, ny);

                    if (f[stu][nx][ny] > f[u.zhuangtai][x][y] + sudu)

                    {

                        f[stu][nx][ny] = f[u.zhuangtai][x][y] + sudu;

                        node temp;

                        temp.zhuangtai = stu;

                        temp.x = nx;

                        temp.y = ny;

                        q.push(temp);

                    }

                }

                //放人

                if (s[nx][ny] == 't')

                {

                    int stu1 = fang1(u.zhuangtai, nx, ny);

                    int stu2 = fang2(u.zhuangtai, nx, ny);

                    if (f[stu1][nx][ny] > f[u.zhuangtai][x][y] + sudu)

                    {

                        f[stu1][nx][ny] = f[u.zhuangtai][x][y] + sudu;

                        node temp;

                        temp.zhuangtai = stu1;

                        temp.x = nx;

                        temp.y = ny;

                        q.push(temp);

                    }

                    if (f[stu2][nx][ny] > f[u.zhuangtai][x][y] + sudu)

                    {

                        f[stu2][nx][ny] = f[u.zhuangtai][x][y] + sudu;

                        node temp;

                        temp.zhuangtai = stu2;

                        temp.x = nx;

                        temp.y = ny;

                        q.push(temp);

                    }

                }

            }

        }

    }

}

int main()

{

    scanf("%d%d%d", &n, &m, &k);

    for (int i = ; i <= n; i++)

    {

        scanf("%s", s[i] + );

        for (int j = ; j <= m; j++)

        {

            if (s[i][j] == 's')

            {

                sx = i;

                sy = j;

            }

            else

            {

                if (s[i][j] == 't')

                {

                    tx = i;

                    ty = j;

                }

                else

                {

                    if (s[i][j] >= 'A' && s[i][j] <= 'Z')

                        top++;

                }

            }

        }

    }

    for (int i = ; i <= top; i++)

        scanf("%s%d", name[i], &speed[i]);

    for (int i = ; i <= ; i++)

        for (int j = ; j <= ; j++)

            for (int l = ; l <= ; l++)

                f[i][j][l] = inf;

    f[][sx][sy] = ;

    bfs();

    printf("%d\n", f[qpow(, top) - ][tx][ty]);

    return ;

}