#include<bits/stdc++.h>
using namespace std;
#define MAXN	16
#define MAXM	32768
#define MAXS	14348907
#define INF	1e9
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int mp[MAXN][MAXN], bit[MAXN];
int ups[MAXM], upt[MAXM];
int sum[MAXN][MAXM], cost[MAXS];
int dp[MAXN][MAXM];
int n, m, goal;
void init() {
	goal = (1 << n) - 1;
	bit[1] = 1;
	for (int i = 2; i <= n; i++)
		bit[i] = bit[i - 1] << 1;
	for (int i = 1; i <= n; i++)
	for (int s = 0; s <= goal; s++) {
		if (s & bit[i]) continue;
		for (int j = 1; j <= n; j++)
			if (s & bit[j]) sum[i][s] += mp[i][j];
	}
	for (int s = 0; s <= goal; s++) {
		int tmp = s, sv = 0, tv = 0, now = 1;
		while (tmp) {
			if (tmp & 1) sv += 2 * now;
			if (tmp & 1) tv += now;
			now *= 3; tmp >>= 1;
		}
		ups[s] = sv; upt[s] = tv;
	}
	for (int s = 0; s <= goal; s++)
	for (int tmp = goal ^ s, t = goal ^ s; t; t = (t - 1) & tmp)
	for (int i = 1; i <= n; i++)
		if (s & bit[i]) cost[ups[s] + upt[t]] += sum[i][t];
}
void update(int &x, int y) {
	x = min(x, y);
}
int main() {
	read(n), read(m);
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		read(x), read(y), read(z);
		mp[x][y] = mp[y][x] = z;
	}
	init();
	for (int i = 1; i <= n; i++)
	for (int j = 0; j <= goal; j++)
		dp[i][j] = INF;
	dp[1][bit[1]] = 0;
	for (int s = 0; s <= goal; s++)
	for (int i = 1; i <= n; i++) {
		if ((bit[i] & s) == 0 || dp[i][s] == INF) continue;
		int ts = s ^ bit[i];
		for (int j = 1; j <= n; j++) {
			if ((bit[j] & s) || mp[i][j] == 0) continue;
			update(dp[j][s ^ bit[j]], dp[i][s] + sum[j][ts]);
		}
		for (int tmp = goal ^ s, t = goal ^ s; t; t = (t - 1) & tmp)
			update(dp[i][s ^ t], dp[i][s] + cost[ups[ts] + upt[t]]);
	}
	cout << dp[n][goal] << endl;
	return 0;
}
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c<=32)c=_buff.get();return c;}
ll qpow(ll x,ll k){return k==0?1:1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
char s[311];
int n,k;
int dp[305][305][305];
void upd(int &x,int v){x=max(x,v);}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	cin>>k;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=n;j>=i;j--)
		{
			for(int t=0;t<=k;t++)
			{
				int cur=dp[i][j][t];
				upd(ans,cur+(s[i]==s[j])*2-(i==j));
				if(t<k)upd(ans,cur+2-(i==j));
				if(i<j)
				{
					upd(dp[i+1][j][t],cur);
					upd(dp[i][j-1][t],cur);
					upd(dp[i+1][j-1][t],cur+(s[i]==s[j])*2-(i==j));
					if(t<k)upd(dp[i+1][j-1][t+1],cur+2-(i==j));
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
