1000s

#include<stdio.h>
#include<string.h>

int moveI[256];
int moveJ[256];

int abs(int x){
    return (x < 0 ? x * -1 : x);
}
int max(int a,int b){
    return (a > b ? a : b);
}
char str[110];
int n;
/*int dp[101][101][101][101];
int cal(int index,int willcut,int I,int J)
{
    if(willcut < 0)return -2e9;
    if(index == n){
        if(willcut != 0)return -2e9;
        return (abs(I) + abs(J))*2;
    }
    if(dp[index][willcut][I][J] != -1)return dp[index][willcut][I][J];
    return dp[index][willcut][I][J] = max(cal(index+1,willcut,I + moveI[str[index]] , J + moveJ[str[index]]),cal(index+1,willcut-1,I,J));
}*/
int posI = 0 , posJ = 0;
int k;
int cal(int index,int cut,int I,int J){
    if(cut == k){
    //  printf("Test (%d,%d) - (%d,%d) = (%d,%d) -> cal : %d\n",posI,posJ,I,J,posI - I,posJ - J,(abs(posI - I) + abs(posJ - J))*2);
        return (abs(posI - I) + abs(posJ - J))*2;
    }
    if(index == n)return -2e9;
    return max(cal(index+1,cut+1,I + moveI[str[index]] , J + moveJ[str[index]]),cal(index+1,cut,I,J));
}
int dp[2][110][210][210];
int main()
{
    moveI['N'] = 1;moveI['S'] = -1;
    moveJ['E'] = 1;moveJ['W'] = -1;

    scanf("%s",str);
    n = strlen(str);
    for(int i=0; i < n ; i++){
        posI += moveI[str[i]];
        posJ += moveJ[str[i]];
    }

    scanf("%d",&k);

    for(int index = 0 ; index < 2 ; index ++){
        for(int cut = k ; cut <= k ; cut ++){
            for(int I = -100 ; I <= 100 ; I ++){
                for(int J = -100 ; J <= 100 ; J ++){
                    dp[index][cut][I+101][J+101] = (abs(posI - I) + abs(posJ - J))*2;
                }
            }
        }
    }
    for(int index = n-1 ; index >= 0 ; index --){
        for(int cut = k-1 ; cut >= 0 ; cut --){
            for(int I = -100 ; I <= 100 ; I ++){
                for(int J = -100 ; J <= 100 ; J ++){
                    dp[index%2][cut][I+101][J+101] = max(dp[(index+1)%2][(cut+1)][I + moveI[str[index]] + 101][J + moveJ[str[index]] + 101],dp[(index+1)%2][cut][I+101][J+101]);
                }
            }
        }
    }
    printf("%d",dp[0][0][101][101]);
//  printf("%d",cal(0,0,0,0));
    return 0;
}