public class GFG  
{ 
    // Function to return the maximized happiness 
    static int maxHappiness(int A, int N, String[] v)  
    { 
        String str; 
  
        // Two arrays similar to 
        // 0 1 knapsack prolem 
        int[] val = new int[N]; 
        int[] wt = new int[N]; 
        int c = 0; 
        for (int i = 0; i < N; i++)  
        { 
            str = v[i]; 
  
            // To store the happiness 
            // of the current goup 
            c = 0; 
            for (int j = 0; j < str.length(); j++)  
            { 
                // Current person is a child 
                if (str.charAt(j) == 'c') 
                    c += 4; 
  
                // Woman 
                else if (str.charAt(j) == 'w') 
                    c += 3; 
  
                // Man 
                else if (str.charAt(j) == 'm') 
                    c += 2; 
  
                // Old Person 
                else
                    c++; 
            } 
  
            // Group's happiness is the sum of happiness 
            // of the people in the group multiplie 
            // the number of people 
            c *= str.length(); 
            val[i] = c; 
            wt[i] = str.length(); 
        } 
  
        // Solution using 0 1 knapsack 
        int[][] k = new int[N + 1][A + 1]; 
        for (int i = 0; i <= N; i++)  
        { 
            for (int w = 0; w <= A; w++)  
            { 
                if (i == 0 || w == 0) 
                    k[i][w] = 0; 
                else if (wt[i - 1] <= w)  
                { 
                    k[i][w] = Math.max(val[i - 1]+ k[i - 1][w - wt[i - 1]], k[i-1][w]); 
                }  
                else 
                { 
                    k[i][w] = k[i - 1][w]; 
                } 
            } 
        } 
        return k[N][A]; 
    } 
  
    // Driver code 
    public static void main(String[] args)  
    { 
        // Number of seats 
        int A = 5; 
  
        // Groups 
        String[] v = { "mmo", "oo", "cmw", "cc", "c" }; 
        int N = v.length; 
        System.out.println(maxHappiness(A, N, v)); 
    } 
} 
  