#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e2+7; 
int dp[maxn][maxn];
int sum[maxn],a[maxn];
signed main(){
	int n;
	cin>>n;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		dp[i][i]=0; 
	}
	for(int len=2;len<=n;len++) {
		for(int l=1;l+len-1<=n;l++) {
			int r=l+len-1;
			for(int k=l;k<r;k++) {
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
			}
		}
	}
	cout<<dp[1][n];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define mod 19650827
const int maxn = 1e3+7;
int a[maxn],dp[maxn][maxn][2];
signed main() {
	int n;
	cin>>n;
	memset(dp,0,sizeof(dp));
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		dp[i][i][0]=1,dp[i][i][1]=0;
	}
	for(int len=2; len<=n; len++) {
		for(int l=1; l+len-1<=n; l++) {
			int r=l+len-1;
			if(a[l]<a[l+1]) {
				dp[l][r][0]+=dp[l+1][r][0];
			}
			if(a[l]<a[r]) {
				dp[l][r][0]+=dp[l+1][r][1];
			}
			if(a[l]<a[r]) {
				dp[l][r][1]+=dp[l][r-1][0];
			}
			if(a[r]>a[r-1]) {
				dp[l][r][1]+=dp[l][r-1][1];
			}
			dp[l][r][0]%=mod;
			dp[l][r][1]%=mod;
		}
	}
	cout<<(dp[1][n][0]+dp[1][n][1])%mod;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+7;
const int Inf = 0x3f3f3f;
struct Point{
	int x,y;
};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n,m,t;
vector<Point>Q;
int dp[17][1<<17];
string s[maxn];
int dis[maxn][maxn];
int f[maxn][maxn];
bool check(int x,int y) {
	if(x>=1&&x<=n&&y>=0&&y<m&&s[x][y]!='#') {
		return 1;
	}
	return 0;
}
void bfs(Point A) {
	queue<Point>q;
	q.push(A);
	memset(dis,0x3f,sizeof(dis));
	dis[A.x][A.y]=0;
	while(!q.empty()) {
		Point u=q.front();
		q.pop();
		for(int i=0;i<4;i++) {
			int dxx=dx[i]+u.x;
			int dyy=dy[i]+u.y;
			if(!check(dxx,dyy)) {
				continue;
			}
			if(dis[dxx][dyy]>dis[u.x][u.y]+1) {
				dis[dxx][dyy]=dis[u.x][u.y]+1;
				q.push({dxx,dyy});
			}
		}
	}
}
int main(){
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++) {
		cin>>s[i];
	}
	int st=0;
	for(int i=1;i<=n;i++) {
		for(int j=0;j<m;j++) {
			if(s[i][j]=='S'||s[i][j]=='T') {
				Q.push_back({i,j});
				if(s[i][j]=='S') {
					st=Q.size()-1;
				}
			}
		}
	}
	int l=Q.size();
	swap(Q[0],Q[st]);
	for(int i=0;i<l;i++) {
		bfs(Q[i]);
		for(int j=0;j<l;j++) {
			f[i][j]=dis[Q[j].x][Q[j].y];
		}
	} 
	memset(dp,0x3f,sizeof(dp));
	dp[0][1]=0;
	for(int i=0;i<(1<<l);i++) {
		for(int j=0;j<l;j++) {
			if(i>>j&1) {
				for(int k=0;k<l;k++) {
					dp[j][i]=min(dp[j][i],f[k][j]+dp[k][i^(1<<j)]);
				}
			}
		}
	}
	int res=Inf;
	for(int i=0;i<l;i++) {
		res=min(res,dp[i][(1<<l)-1]+f[i][0]);
	}
	cout<<((res==Inf)?-1:(1ll*(l-1)*t+1ll*res));
	return 0;
}