DP level 2

class Solution {
    
    //using rabin karp rolling hash algo to replace text.substring ->O(n) to O(1)
    //which makes the whole algo O(n^2)
    private static final int PRIME = 101;
    private static final int MOD = 1_000_000_007;
    public int distinctEchoSubstrings(String text) {
        /*  Q66 of dp playlist , echo substring(ess)
        */
        
        int n = text.length();
        
        // dp[i][j] : hash value of text[i:j]
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            long hash = 0;
            for (int j = i; j < n; j++) {
                hash = hash * PRIME + (text.charAt(j) - 'a' + 1);
                hash %= MOD;
                dp[i][j] = (int) hash;
            }
        }

        //make a HS to store distinct echo substrings
        HashSet<Integer> set = new HashSet<>();

        //checking all ess of length 2->n/2
        for(int len = 1 ; len <= n/2 ; len++){

            /* we keep checking characters at a gap of length and increasing count
            if chars are equal we keep the count going for potential ess ,if chars
            are not equal our current potential ess is ruined and we start checking
            again for new ess from count = 0

            if count = len , we add the substring in the HS and count-- to check if
            the next characters are making and ess , basically it means deleting
            a character from behind and continue checking to find next ess
            */
            int count = 0;
            for(int i = 0,j = len ;j < n ; i++ , j++){
                
                char ch1 = text.charAt(i) , ch2 = text.charAt(j);

                if(ch1 == ch2)
                count ++;

                else
                count = 0;

                if(count == len){
                //here instead of substring function we store a unique hashvalue for i to jth string in dp
                    set.add(dp[i][j]);
                    count --;
                }
            }
        }
        System.out.print(set);
        return set.size();
    }
}

class Solution {
    public int distinctEchoSubstrings(String text) {
        /*  Q66 of dp playlist , echo substring(ess)
        */

        int n = text.length();
        //make a HS to store distinct echo substrings
        HashSet<String> set = new HashSet<>();

        //checking all ess of length 2->n/2
        for(int len = 1 ; len <= n/2 ; len++){

            /* we keep checking characters at a gap of length and increasing count
            if chars are equal we keep the count going for potential ess ,if chars
            are not equal our current potential ess is ruined and we start checking
            again for new ess from count = 0

            if count = len , we add the substring in the HS and count-- to check if
            the next characters are making and ess , basically it means deleting
            a character from behind and continue checking to find next ess
            */
            int count = 0;
            for(int i = 0,j = len ;j < n ; i++ , j++){
                
                char ch1 = text.charAt(i) , ch2 = text.charAt(j);

                if(ch1 == ch2)
                count ++;

                else
                count = 0;

                if(count == len){
                    String str = text.substring(i - (len-1), j+1);
                    set.add(str);
                    count --;
                }
            }
        }
        System.out.print(set);
        return set.size();
    }
}

class Solution {
    public boolean canCross(int[] stones) {
        /* Q64 of dp playlist , in this question we need to store the jumps which
        has been made from the previous stone for that we make a HM<stones , HS>
        to store the allowed jumps

        we traverse the array and keep updating the next stones allowed jumps,
        if we end up on any stone which has its jumps hashset = 0 we return false
        if we end on last stone we return true;
        */
    
        //make a hashmap to store allowed jumps
        HashMap<Integer,HashSet<Integer>> map = new HashMap<>();
        int n = stones.length;

        //fill the hashmap and initialise the HS
        for(int i = 0 ; i < n ; i++)
        map.put(stones[i] , new HashSet<>());

        //adding jumps for 0th and 1st stone;
        map.get(0).add(1);
        
        //traverse the array
        for(int i = 0 ; i < n ; i++){
            
            //taking out allowed jumps
            HashSet<Integer> jumps = map.get(stones[i]);

            //check all jumps in jumps hashset
            for(int jump : jumps){
                System.out.print(" " + stones[i] +" "+ jump+ "\n" );
                
                boolean validJump = map.containsKey(stones[i] + jump);
                
                //if after jumping we end on a valid stone update the jumps of 
                //the valid stone 
                if(validJump == true){
                    HashSet<Integer> nextStone = map.get(stones[i] + jump);

                    nextStone.add(jump);
                    nextStone.add(jump + 1);
                    
                    //we cannot add 0 jumps
                    if(jump != 1)
                    nextStone.add(jump - 1);

                    map.put(stones[i] + jump , nextStone);
                    
                }
            }
        }

        if(map.get(stones[n-1]).size() > 0){
            // System.out.println(map);
            return true;
        }

        else{
            // System.out.println(map);
            return false;
        }
        
    }
}

class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        /* Q63 of dp playlist , the tower is nothing but a 2d array , make a 2d dp
        of size k+1(to be on safe side) , and simply find spare for each glass
        and pass on spare/2 to both glasses below it 

        travel the dp from left to right 
        */
        double[][] dp = new double[102][102];
        dp[0][0] =(double) poured;   //adding water to the first glass

        for(int i = 0 ; i <= query_row ; i++){

            for(int j = 0 ; j <= i ; j++){
                //calculating spare and filling both glasses directly below
                //if the current glass has overflow 
                if(dp[i][j] > 1.0){
                    double spare = dp[i][j] - 1.0;
                    dp[i+1][j] += spare / 2.0; 
                    dp[i+1][j+1] += spare / 2.0;

                    dp[i][j] = 1.0;
                }
            }
        }

        return dp[query_row][query_glass];
    }
}

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        /* Q62 of dp playlist , every cell denotes ith ugly number . here we make
        a pointers array to store pointer for all factors which are in primes 
        array. rest same approach as ugly numbers.

        we apply 2 loops 1-> to check the minimum of all values given by factors
        and 2-> to update the indexes of pointers
        */
        int m = primes.length;
        
        long[] dp = new long[n+1];   //we have to return nth ugly number
        dp[1] = 1;  //1 is the first ugly number

        int[] pointers = new int[m];
        Arrays.fill(pointers , 1);  //all primes pointers points at one in begning

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

            //1st loop to find min of all values
            long min = Integer.MAX_VALUE;
            for(int j = 0 ; j < m ; j++){
                long valf = (long)primes[j] * (long)dp[pointers[j]];

                min = Math.min(min , valf);
            }
            dp[i] = min;    //storing min value in dp

            //now incrementing indexes of pointers for primes which gave min value
            for(int j = 0 ; j < m ;j++){
                long valf = (long)primes[j] * (long)dp[pointers[j]];
                
                if(valf == min)
                pointers[j] ++;
            }
            
        }
        
        // for(int i = 0 ;i <= n ; i++)
        // System.out.print(dp[i] + " ");
        
        return (int)dp[n];
    }
}

class Solution {
    public boolean isUgly(int n) {
        /* Q61 dp playlist , every cell denote ith ugly number . we make 3 
        pointers for 2,3,5 keeping every pointer at 1 . we traverse the dp and 
        find next ugly number by multiplying prev ugly number by all 3 factors
        and taking minimum of all and moving pointer which gave minimum value by
        1.
        -> if more than 1 pointer gives the same minimum value we both all such
        pointers by 1
        */
        if(n == 1)return true;

        int[] dp = new int[n+1];
        dp[1] = 1;  //1 is 1st ugly number
        
        int f2 = 1 , f3 = 1 , f5 = 1;

        for(int i = 2 ; i <= n ; i++){
            int val2 = 2 * dp[f2] , val3 = 3 * dp[f3] , val5 = 5 * dp[f5];

            //ugly number will be min of all vals
            dp[i] = Math.min(val2 , Math.min(val3,val5));

            //updating pointers
            if(dp[i] == val2) f2++;
            if(dp[i] == val3) f3++;
            if(dp[i] == val5) f5++;

            //if before reaching n 
            if(dp[i] == n)
            return true;

            // else if(dp[i] > n)
            // return false;
        }

        for(int i = 0 ;i < n ; i++)
        System.out.print(dp[i] + " ");

        return false;
    }
}

class Solution {
    public int minInsertions(String s) {
        /* Q60 of dp playlist , find longest pallindromic subsequnce 
        then minimum insertion to make strings pallindromic becomes
                    str.length() - LPS;
        */

        //code of LPS
        int n = s.length();
        int[][] dp = new int[n][n];

        for(int gap = 0 ; gap < n ; gap++){
            for(int i = 0 , j = gap ; j < n ; j++,i++){

                if(gap == 0)
                dp[i][j] = 1;

                else if(gap == 1)
                dp[i][j] = s.charAt(i)==s.charAt(j) ? 2 :1;

                else{
                    char ch1 = s.charAt(i) , ch2 = s.charAt(j);

                    if(ch1 == ch2)
                    dp[i][j] = dp[i+1][j-1] + 2;

                    else
                    dp[i][j] = Math.max(dp[i][j-1] , dp[i+1][j]);
                }
            }
        }

        //minimum insertions becomes
        return s.length() - dp[0][n-1];

    }
}

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;

class GFG{
    public static void main(String args[])throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        while(t-- > 0){
            int N = Integer.parseInt(in.readLine());
            String a[] = in.readLine().trim().split("\\s+");
            int arr[] = new int[N];
            for(int i = 0; i < N;i++)
                arr[i] = Integer.parseInt(a[i]);
            
            Solution ob = new Solution();
            System.out.println(ob.offerings(N, arr));
        }
    }
}
// } Driver Code Ends


//User function Template for Java

class Solution{
    int offerings(int n, int arr[]){
        /* Q59 of dp playlist , we traverse from left to right the temple and assign
        prev + 1 if we encounter a greater value else 1 , we do the same thing from right
        to left .
        
        we do this method inorder to get correct estimation of the no.downhill .for eg
        if uphill is 1 2 3 4 and then downhilll will be 3 2 1 0 -1 -2 -3 but we cant 
        give negative offering therefore we traverse from left to right also to get
        correct estimation of by taking max of (left ,right)
        */
        int left[] = new int[n] , right[] = new int[n];
        
        //left to right traverse
        left[0] = 1;
        for(int i = 1 ; i < n ;i++){
            
            //if we encounter greater temple we offer prev+1 offering
            if(arr[i] > arr[i-1])
            left[i] = left[i-1] + 1;
            
            //else offering resets to 1
            else
            left[i] = 1;
        }
        
        //similiarly for right to left 
        right[n-1] = 1;
        for(int i = n-2 ; i >=0 ; i--){
            
            if(arr[i] > arr[i+1])
            right[i] = right[i+1] +1;
            
            else
            right[i] = 1;
        }
        
        int ans = 0;
        
        //our answer will be correct estimation of temples offering which we will get 
        //by taking max of left and right for each temple
        for(int i = 0 ;i < n ; i++)
        ans += Math.max(left[i],right[i]);
        
        return ans;
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        /* Q58 of dp , every cell will store total no.of sentences which can be
        made using ith string , we have solved this question for total no. of 
        sentences which can be made from s for words in dictionary
        */

        HashSet<String> set = new HashSet<>(wordDict);
        int n = s.length();
        int[] dp = new int[n];

        for(int i =0 ; i < n ;i++){
            //checking all suffix of ith string
            for(int j = 0 ; j <= i  ; j++){
                String temp = s.substring(j , i+1);

                //if ith string is in dictionary 
                if(set.contains(temp)){
                    /* if the suffix word is in dictionary add that word in the
                    of all sentences which are made by dp[j-1];
                    */
                    if(j > 0)
                    dp[i] += dp[j-1];

                    //if the whole substring exist in the dictionary add +1 for
                    //that individual word
                    else //j==0
                    dp[i] += 1;
                }
            }
        }

        //if dp[n-1] has any valid sentences it will be greater than 0
        return dp[n-1] > 0 ? true : false;
    }
} 

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        /* Q57 of dp playlist , every cell denotes total no. of subarrays APs 
        of size >=2 ending at that ith element. here dp is an array of HM
        
        we make a HM[] to store common difference -> no.of Ap for all elements
        */
        int n = nums.length , ans = 0;
        //making HM
        HashMap<Integer,Integer>[] map = new HashMap[n];

        //iniitalizing all hashmap in hashmap[]
        for(int i = 0 ; i < n ; i++)
        map[i] = new HashMap<>();

        //common approach of LIS
        for(int i = 1 ; i < n ;i++){

            for(int j = i-1 ; j >= 0 ; j--){
                long cd = (long)nums[i]-(long)nums[j];

            //edge case if cd goes out of integer range
            if(cd <= Integer.MIN_VALUE || cd >= Integer.MAX_VALUE)continue;
            
        /*we traverse the array in LIS fashion to store subarray ap of size >=2
        for each element if at any moment we find that the common difference 
        found by nums[i] - nums[j] already exists that means current element 
        is going to be the 3rd or more member of the AP so now total no. of
        AP's  of length >=3 increases by 1 and we add to the answer */
                if(map[j].containsKey((int)cd)){
                    int AP = map[j].get((int)cd);

                    map[i].put((int)cd , map[i].getOrDefault((int)cd,0) + AP+1);
                    ans += AP;
                }
        /* if its a new (cd then we just add it to the map and they become a 2
        sized ap , if in the future some number has same common difference it
        will add to this AP 
        */
                else
                map[i].put((int)cd , map[i].getOrDefault((int)cd,0)+1);

            }
        }
        return ans;
    }
}

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        /* Q56 of dp playlist , every cell denotes no. of subarrays of dp which
        ends in ith element , our answer will be total sum of all such subarrays
        stored in dp
        */

        //making dp
        int n = nums.length;

        if( n < 3) return 0;    //we need >= 3 elements for an AP

        int[] dp = new int[n];

        //we skip the first 2 elements 
        int ans = 0 ;
        for(int i = 2 ; i < n ; i++){
            int val1 = nums[i] - nums[i-1];
            int val2 = nums[i-1] - nums[i-2];
            
            /*we check if the common difference is same ith element will have 
            +1 ap than the previous element
            */
            if(val1 == val2)
            dp[i] = dp[i-1] +1;

            else
            dp[i] = 0;
            
            //answer will be sum of all 
            ans += dp[i];
        }

        return ans;
    }
}

int n = arr.length;
 
		int[] winSum = new int[n];
 
		for(int i = 0; i <= n - k; i++){
 
            if(i == 0){
 
                for(int j = 0; j < k; j++){
 
                    winSum[i] += arr[j];
 
                }
 
            }else{
 
                winSum[i] = winSum[i - 1] + arr[i + k - 1] - arr[i - 1];
 
            }
 
        }
 
        
 
		int[][] dp = new int[m + 1][arr.length + 1];
 
		for(int i = 0; i < dp.length; i++){
 
		    for(int j = 0; j < dp[0].length; j++){
 
		        if(i == 0){
 
		            dp[i][j] = 0;
 
		        }else if(j < i * k){
 
		            dp[i][j] = 0;
 
		        }else{
 
		            dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - k] + winSum[j - k]);
 
		        }
 
		    }
 
		}
 
		return dp[m][arr.length];

// Java program to find Max sum
// of M non-overlapping subarray
// of size K in an Array

import java.io.*;

class GFG
{
// calculating presum of array.
// presum[i] is going to store
// prefix sum of subarray of
// size k beginning with arr[i]
static void calculatePresumArray(int presum[],
								int arr[],
								int n, int k)
{
	for (int i = 0; i < k; i++)
	presum[0] += arr[i];

	// store sum of array index i to i+k
	// in presum array at index i of it.
	for (int i = 1; i <= n - k; i++)
	presum[i] += presum[i - 1] + arr[i + k - 1] -
								arr[i - 1];
}

// calculating maximum sum of
// m non overlapping array
static int maxSumMnonOverlappingSubarray(int presum[],
										int m, int size,
										int k, int start)
{
	// if m is zero then no need
	// any array of any size so
	// return 0.
	if (m == 0)
		return 0;

	// if start is greater then the
	// size of presum array return 0.
	if (start > size - 1)
		return 0;

	int mx = 0;

	// if including subarray of size k
	int includeMax = presum[start] +
			maxSumMnonOverlappingSubarray(presum,
					m - 1, size, k, start + k);

	// if excluding element and searching
	// in all next possible subarrays
	int excludeMax =
			maxSumMnonOverlappingSubarray(presum,
						m, size, k, start + 1);

	// return max
	return Math.max(includeMax, excludeMax);
}

// Driver code
public static void main (String[] args)
{
	int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
	int n = arr.length;
	int m = 3, k = 1;
	int presum[] = new int[n + 1 - k] ;
	calculatePresumArray(presum, arr, n, k);
	
	// resulting presum array
	// will have a size = n+1-k
	System.out.println(maxSumMnonOverlappingSubarray(presum,
										m, n + 1 - k, k, 0));
}
}

// This code is contributed by anuj_67.

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        /* Q54 of dp playlist
        */

        //making 3 arrays left ,right and PSA
        int n = nums.length;
        int[] left = new int[n] , right = new int[n] , psa = new int[n];

        //making prefix sum array
        for(int i = 0 ;i < n ;i++){
            if(i==0)
            psa[i] = nums[i];
            
            else 
            psa[i] = psa[i-1] + nums[i];
        }

        //now making left and right dp arrays
        int sum1 = 0 , sum2 = 0;
        for(int i = 0 , j = n-1 ; i < n ; i++ ,j--){

            if(i < k){
                sum1 += nums[i];
                left[i] = sum1;
            }
            else{
                sum1 += nums[i] - nums[i-k];
                left[i] = Math.max(sum1 , left[i-1]);
            }

            if(j+k >= n){
                sum2 += nums[j];
                right[j] = sum2;
            }
            else{
                sum2 += nums[j] - nums[j+k];
                right[j] = Math.max(sum2 , right[j+1]);
            }
        }

        //now traversing the middle array and finding max combination of 
        //left + middle + right and also finding the indexes of all 3 arrays
        
        int ans = Integer.MIN_VALUE;
        int li = -1 , mi = -1 , ri = -1;    //left idx ,middle idx , right idx
        for(int i = k ; i <= n - 2*k ; i++){
            int middle = psa[i + k -1] - psa[i-1];
            
            int val = left[i-1] + right[i+k] + middle;
            
            if(val > ans){
                ans = val;
                li = left[i-1] ; mi = i ; ri = right[i+k];
            }
        }

        // System.out.println(li + " " + mi + " " + ri);
        /* now that we have the indexes of all 3 we can find lexiographically
        first index of all 3 subarray by storing the first value which comes 
        for left ,right
        */
        

        // for(int i = 0 ;i < n ; i++)
        // System.out.print(left[i] + " ");

        // System.out.println();

        // for(int i = 0 ;i < n ; i++)
        // System.out.print(right[i] + " ");
        
        // System.out.println();
        
        //finding lexiographically first index of left by comparing value of Li
        
        for(int i = k-1 ; i <= mi-1 ; i++){
            if(psa[i] - (i-k < 0 ? 0 : psa[i-k])==li){
                li = i-k+1;
                break;
            }
        }

        //finding lexiographically first index of right by comparing value of Ri
        for(int i = mi + (2 * k)-1 ; i < n ; i++){
            if(psa[i] - psa[i-k] == ri){
                ri = i-k+1;
                break;
            }
        }

        // System.out.println(li + " " + mi + " " + ri);

        int[] list = {li , mi , ri};
        return list;
    }
}

class Solution {
    
    public int function(int[] nums , int x , int y){
        //making dp 
        int n = nums.length;
        int[] dp1 = new int[n];     //dp for MSA of x size
        int[] dp2 = new int[n];     //dp for MSA of y size

        int sum1 = 0 , sum2 = 0;
        for(int i = 0 , j = n-1 ; i < n ; i++ , j--){
            int val = nums[i];
            //if ith index is smaller than x store sum only
            if(i < x){
                sum1 += val;
                dp1[i] = sum1;
            }
            //else check which is larger previous MSAx or sum including current 
            //element
            else{
                sum1 += nums[i] - nums[i-x];
                dp1[i] = Math.max(dp1[i-1] ,sum1);
            }

            int val2 = nums[j];

            //we fill 2nd array right to left 
            if(j + y  >= n){
                sum2 += val2;
                dp2[j] = sum2;
            }
            //else check which is larger previous MSAy or sum including current 
            //element
            else{
                sum2 += nums[j] - nums[j+y];
                dp2[j] = Math.max(dp2[j+1] , sum2);
            }
        }

        int ans = 0;

        //assuming x size MSA to be first and y size MSA to be 2nd
        for(int i = x-1 ; i < n-y ; i++)
        ans = Math.max(ans , dp1[i] + dp2[i+1]);

        return ans;
    }
    
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        /* Q53 dp playlist ,we use kadane's algo to find MSA for x size and y
        size respectively for every element and then take max(MSAx + MSAy)for
        all indexes

        we fill 2nd dp right to left and 1st dp left to right

        similiarly we do the same this time assuming y size has occured first 
        and then x size has occured and do the same

        finally we return max value of the two values obtained
        */
        
        //assuming firstlen exists 1st and secondlen exists 2nd
        int ans1 = function(nums , firstLen , secondLen);

        //assuming firstlen exists 2nd and secondlen exists 1st
        int ans2 = function(nums , secondLen , firstLen);

        return Math.max(ans1 , ans2);
    }
}

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;

class GFG {
    public static void main(String args[]) throws IOException {
        BufferedReader read =
            new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(read.readLine());
        while (t-- > 0) {
            
            String s = read.readLine();
            Solution ob = new Solution();
            System.out.println(ob.maxSubstring(s));
        }
    }
}
// } Driver Code Ends


//User function Template for Java

class Solution {
    int maxSubstring(String s) {
        /* Q52 of dp playlist , making 0's to 1 and 1's to -1 and then applying
        kadane's algo to find max sum sub array which will also give use the 
        max difference between 0's and 1's
        */
        
        //applying kadanes
        int csum = 0 , omax = Integer.MIN_VALUE;
        
        for(int i =0 ; i < s.length() ; i++){
            char ch = s.charAt(i);
            int val = 0;
            
            if(ch == '0')
            val = 1;
            
            else
            val = -1;
            
            if(csum > 0)
            csum += val;
            
            else
            csum = val;
            
            omax = Math.max(csum , omax);
        }
        return omax;
    }
}

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;
class GfG
{
    public static void main(String args[])
        {
            Scanner sc = new Scanner(System.in);
            int t = sc.nextInt();
            while(t-->0)
                {
                    int n = sc.nextInt();
                    Solution ob = new Solution();
                    System.out.println(ob.getCount(n));
                }
        }
}    
// } Driver Code Ends


//User function Template for Java

class Solution
{
	public long getCount(int n)
	{
	    /*Q51 dp playlist , 
		*/
		long ans = 0;
		//make dp , keep no.of presses on rows and keypad nums on cols
		long[][] dp = new long[n+1][10];
		
		//store the info of which keypads can be pressed for which keypads
		int[][] data = {
		    {0,8},
		    {1,2,4},
            {1,2,3,5},
            {3,2,6},
            {4,1,5,7},
            {4,5,6,2,8},
            {3,6,9,5},
            {4,7,8},
            {5,7,8,9,0},
            {6,8,9}
		};
	
		//i==0 will be all 0 by default
		for(int i = 1 ; i <= n ; i++){
		    
		    for(int j = 0 ; j <= 9 ; j++){
		        
		        //if 1st row only 1 number can be created with 1 press
		        if(i==1)
		        dp[i][j] = 1;
		        
		        /* if more than 1 press add all the (i-1)th press numbers generated
		        for all numbers which can be pressed after current key stored in data[]
		        */
		        else{
		            for(int prev : data[j])
		            dp[i][j] += dp[i-1][prev];
		        }
		    }
		}
		
		//total numbers can be created with n presses will be sum of last row 
		for(int j = 0; j <= 9 ; j++)
		ans += dp[n][j];
		
		return ans;
	}
}

import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;

public class main {
    
    public static int solution(String s1 , String s2 ){//s2 is target
        //tabulization approach -> every cell denotes total no. of way of making 
        //ith string from jth string if only deletion is allowed
        
        //make dp with target on rows and source on coloumns
        int n = s1.length() , m = s2.length();
        int dp[][] = new int[m+1][n+1];
        
        for(int i = m ; i>=0 ; i--){
            for(int j = n ; j>=0 ; j--){
                //if last cell ->1
                if(i == m & j==n)
                    dp[i][j] =1;
                //if last row ->1
                else if(i == m)
                    dp[i][j] = 1;
                //if last col -> 0
                else if(j == n)
                    dp[i][j] = 0;
                
                //rest of the dp
                else{
                    char ch1 = s2.charAt(i) , ch2 = s1.charAt(j);
                    //if chars are not equal we remove character from source
                    if(ch1 != ch2)
                        dp[i][j] = dp[i][j+1];
                    
                    //if chars are equal we remove character from source & we match
                    //both characters
                    else
                        dp[i][j] = dp[i+1][j+1] + dp[i][j+1];
                }
            }
        }
        
        for(int i = 0 ; i < dp.length ; i++){
            for(int j = 0 ; j < dp[0].length ; j++)
                System.out.print(dp[i][j] + " ");
            
            System.out.println();
        }
        return dp[0][0];
    }
    public static void main(String[] args) throws Exception {   
         Scanner scn = new Scanner(System.in);
        String s1 = scn.next();
        String s2 = scn.next();
        
        int[][] dp = new int[s1.length()][s2.length()];
        
        System.out.println(solution(s1, s2 ));
    }
}

import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;

public class main {
    
    public static int solution(String s1 , String s2 , int si ,int ti , int[][] dp){
        //base case if target ends
        if(ti == s2.length())
            return 1;
        
        //if source string ends
        else if(si == s1.length())
            return 0;
        
        //memoization , if answer is already calculated return it
        if(dp[si][ti] != -1)
            return dp[si][ti];
        
        //taking out characters
        char ch1 = s1.charAt(si) , ch2 = s2.charAt(ti);
        
        int totalways = 0;
        //if chars are not equal we delete source character and give a call
        if(ch1 != ch2)
            totalways = solution(s1 , s2 , si+1 , ti , dp);
        
        //if chars are equal we give 2 calls 1 with both matching other with removing
        //only source character
        else{
            int tw1 = solution(s1,s2,si+1,ti+1,dp);
            int tw2 = solution(s1,s2,si+1,ti,dp);
            
            totalways = tw1 + tw2;
        }
        
        dp[si][ti] = totalways;
        
        return totalways;
    }
    public static void main(String[] args) throws Exception {   
         Scanner scn = new Scanner(System.in);
        String s1 = scn.next();
        String s2 = scn.next();
        
        int[][] dp = new int[s1.length()][s2.length()];
        
        for(int i = 0 ; i < dp.length ; i++){
            for(int j = 0 ; j < dp[0].length ; j++)
                dp[i][j] = -1;
        }
        
        System.out.println(solution(s1, s2 , 0 ,0 , dp));
    }
}

import java.util.* ;
import java.io.*; 
 
public class Solution {

	public static int highwayBillboard(int[] billboards, int[] revenue, int m, int x) {
	 	//making a HM to store billboards and their revenue
		 HashMap<Integer,Integer> map = new HashMap<>();

		 for(int i = 0 ; i < billboards.length ; i++)
		 map.put(billboards[i],revenue[i]);

		 //making dp 
		 int dp[] = new int[m+1];	//+1 for 0th mile
		 dp[0] = 0;
		 
		 for(int i =1 ; i <= m ; i++){

			 //if there exists a billboard on ith mile
			 if(map.containsKey(i)){
				 int boardNotInstalled = dp[i-1];
				 int boardInstalled = map.get(i);

				//we add dp[i- x-1] only when ith mile is greater than x+1
					if(i >= x+1)
					boardInstalled += dp[i- x-1];
				 dp[i] = Math.max(boardInstalled,boardNotInstalled);
			 }
			 else
			 dp[i] = dp[i-1];
		 }

		 return dp[m];
	}

}

import java.util.* ;
import java.io.*; 
 
public class Solution {

	public static int highwayBillboard(int[] billboards, int[] revenue, int m, int x) {
		/* Q49 dp playlist ,first approach same as LIS , we find max while
		applying LIS here we have to make sure 2 billboards are placed at a
		greater distance of x , which becomes the constraint between i and j
		*/
			int ans = Integer.MIN_VALUE;
			int dp[] = new int[revenue.length];
			dp[0]=revenue[0];
			
			for(int i = 1 ; i < dp.length ;i++){
				
				int profit = revenue[i];
				for(int j = i-1 ; j >=0 ; j--){
					int potential = dp[j] + revenue[i];

					if(billboards[i] - billboards[j] > x)
					profit = Math.max(potential , profit);
				}
				dp[i] = profit;

				ans = Math.max(ans , dp[i]);
			}
			return ans;
		
	}

}

class Solution {
    
    public boolean isValid(int ni , int nj , int n ){

        if(ni < 0 || nj < 0 || ni >= n || nj >= n)
        return false;

        return true;
    }
    public double knightProbability(int n, int k, int row, int col) {
        /* Q48 in dp playlist ,current represent current instance of the board,
        next represent next instance of the board in the end we swap curr &
        next and make next to 0 again so that we can use it store the prob of
        next moves which will impact the board cells

        in the end we loop over the latest board and add all the probibilites
        on all cell which will give us probibility that knight remains on the 
        board
        */

        double[][] curr = new double[n][n];
        double[][] next = new double[n][n];

        //making a direction array to loop over for the knights 8 moves
        int[][] dir = {{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};

        //for the very first instance probibility of center cell will be 1
        curr[row][col] = 1;

        //looping for k moves
        for(int moves = 0 ; moves < k ; moves++){
            
        //looping the current board and storing effect of knight move on next
            for(int i = 0 ; i < n ; i++ ){

                for(int j = 0 ; j < n ; j++){
                    
                    if(curr[i][j] != 0){
                        int ni = 0 , nj = 0;    //next i , next j
                        for(int d = 0 ; d < 8 ; d++){
                            ni = i + dir[d][0];
                            nj = j + dir[d][1];

                            if(isValid(ni,nj,n))
                            next[ni][nj] += curr[i][j]/8.0;
                        }
                    }
                }
            }
        //to store the probibilities of next move we do the following 
            curr = next;
            next = new double[n][n];
        }

        //now we add all the probibilites of the latest board and return it 
        double prob = 0;
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++)
            prob += curr[i][j];
        }

        return prob;
    }
}

class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][][][] dp = new int[n][n][n][n];
        return cherry(0 , 0 , 0 , 0 , grid , dp , n);
    }

    public static int cherry(int r1 , int c1 , int r2 , int c2 , int[][] grid ,int[][][][] dp , int n)
    {
        //if invalid move return -infinity as there is no way to reach last cell
        if(r1 >= n || r2 >= n || c1 >= n ||
        c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1)
        return -1;

        //if 1 person is at last cell it means other will also be at last cell
        if(r1 == n - 1 && c2 == n - 1)
        return grid[r1][c1];
        
        //if answer is already stored in memoization return it
        if(dp[r1][c1][r2][c2] != 0)
        return dp[r1][c1][r2][c2];

        int cherries = 0;
        
        //if both person are at same cell , add it only once 
        if(r1 == r2 && c1 == c2)
        cherries += grid[r1][c1];

        else
        cherries += grid[r1][c1] + grid[r2][c2];

        int f1 = cherry(r1 , c1+1 , r2 , c2+1 , grid,dp,n);  //hh
        int f2 = cherry(r1 , c1+1 , r2+1 , c2 , grid,dp,n);  //hv
        int f3 = cherry(r1+1 , c1 , r2+1 , c2 , grid,dp,n);  //vv
        int f4 = cherry(r1+1 , c1 , r2 , c2+1 , grid,dp,n);  //vh

        cherries += Math.max(Math.max(f1,f2),Math.max(f3,f4));
        dp[r1][c1][r2][c2] = cherries;
        return cherries;
    }
}

class Solution {
    public int superEggDrop(int eggs, int floors) {
        //dp ques 46 of playlist


        //if floors == 1 return 1 , if 0 return 0 ;
        if(floors == 0) return 0 ;
        if(floors == 1) return 1;  
        if(eggs == 0)  return -1;
        if(eggs == 1) return floors;    //minimum attempts will be total floors

        //let eggs be on rows and floors be on cols

        //+1 for 0 eggs and 0 floors
        int dp[][] = new int[eggs+1][floors+1]; 

        //1st row ->invalid , 2nd row -> no.of floors will be answer ,1st col->0
        for(int i = 1 ; i < eggs+1 ;i++){
            for(int j = 1 ; j < floors+1 ; j++){

                if(i == 1)
                dp[i][j] = j;

                else{
                    // taking max of all options and then taking min of those
    
                    int min = Integer.MAX_VALUE;
                    for(int b = j-1 , a = 0 ; b>=0 ; a++ , b--){
                        int breaks = dp[i][b];  //egg breaks
                        int safe = dp[i-1][a];   //egg doesn't breaks

                        int val = Math.max(safe , breaks);
                        min = Math.min(val , min);
                    }
                    dp[i][j] = min+1;
                }
            }
        }
        
        return dp[eggs][floors];
    }
}

class Solution {
    public boolean PredictTheWinner(int[] arr) {
        //dp playlist ques - 45 , use of gap strategy
        
        //finding total
        int n = arr.length , total = 0;

        for(int i = 0 ; i < n ; i++)
        total += arr[i];

        //making the dp
        int [][]dp = new int[n][n];
        
        //traversing & handling trivial cases and rest of the dp
        for(int gap = 0 ; gap <  n ; gap++){
            
            for(int i = 0 , j = gap ; j < n ; i++ , j++){
                
                //when only one coin
                if(gap == 0)
                dp[i][j] = arr[i];  //i==j
                
                //when only 2 coin, you take maximum of 2
                else if(gap == 1)
                dp[i][j] = Math.max(arr[i],arr[j]);
                
                //when more than 2 coins
                else{
                    /* if you chose ith coin , the opponent will choose the
                    next coin such that you get minimum of next choice
                    */
                    int cost1 = arr[i] + Math.min(dp[i+2][j],dp[i+1][j-1]);
                    
                    /* if you chose ith coin , the opponent will choose the
                    next coin such that you get minimum of next choice
                    */
                    int cost2 = arr[j] + Math.min(dp[i+1][j-1] , dp[i][j-2]);
                    
                    //but you will make choices such that you get max of cost1
                    //and cost2
                    dp[i][j] = Math.max(cost1 , cost2);
                }
            }
        }
        //now your final maximum score is in dp[0][n-1] , opponent score will be
        int opponent = total - dp[0][n-1];
        
        //if opponent score is greater than yours return false else true
        return opponent > dp[0][n-1] ? false : true;
    }
}

//{ Driver Code Starts
import java.util.*;
import java.io.*;
import java.lang.*;

class OptimalStrategy
{
    public static void main (String[] args) {
        
        //taking input using Scanner class
        Scanner sc = new Scanner(System.in);
        
        //taking total number of testcases
        int t = sc.nextInt();
        
        while(t-- > 0)
        {
            //taking number of elements
            int n = sc.nextInt();
            int arr[] = new int[n];
            
            //inserting the elements
            for(int i = 0; i < n; i++)
                arr[i] = sc.nextInt();
                
           //calling the countMaximum() method of class solve
           System.out.println(new solve().countMaximum(arr, n)); 
        }
    }
    
    
}
// } Driver Code Ends



class solve
{
    //Function to find the maximum possible amount of money we can win.
    static long countMaximum(int arr[], int n)
    {
        //dp playlist ques - 45 , use of gap strategy
        
        //making the dp
        int [][]dp = new int[n][n];
        
        //traversing & handling trivial cases and rest of the dp
        for(int gap = 0 ; gap <  n ; gap++){
            
            for(int i = 0 , j = gap ; j < n ; i++ , j++){
                
                //when only one coin
                if(gap == 0)
                dp[i][j] = arr[i];  //i==j
                
                //when only 2 coin, you take maximum of 2
                else if(gap == 1)
                dp[i][j] = Math.max(arr[i],arr[j]);
                
                //when more than 2 coins
                else{
                    /* if you chose ith coin , the opponent will choose the next coin
                    such that you get minimum of next choice
                    */
                    int cost1 = arr[i] + Math.min(dp[i+2][j],dp[i+1][j-1]);
                    
                    /* if you chose ith coin , the opponent will choose the next coin
                    such that you get minimum of next choice
                    */
                    
                    int cost2 = arr[j] + Math.min(dp[i+1][j-1] , dp[i][j-2]);
                    
                    
                    //but you will make choices such that you get max of cost1 and cost2
                    dp[i][j] = Math.max(cost1 , cost2);
                }
            }
        }
        
        return dp[0][n-1];
        //returning answer
    }
}
  
  
  
  
  
  
  
  
  
  
  //{ Driver Code Starts
import java.util.*;
import java.io.*;
import java.lang.*;

class OptimalStrategy
{
    public static void main (String[] args) {
        
        //taking input using Scanner class
        Scanner sc = new Scanner(System.in);
        
        //taking total number of testcases
        int t = sc.nextInt();
        
        while(t-- > 0)
        {
            //taking number of elements
            int n = sc.nextInt();
            int arr[] = new int[n];
            
            //inserting the elements
            for(int i = 0; i < n; i++)
                arr[i] = sc.nextInt();
                
           //calling the countMaximum() method of class solve
           System.out.println(new solve().countMaximum(arr, n)); 
        }
    }
    
    
}
// } Driver Code Ends



class solve
{
    //Function to find the maximum possible amount of money we can win.
    static long countMaximum(int arr[], int n)
    {
        //dp playlist ques - 45 , use of gap strategy
        
        //making the dp
        int [][]dp = new int[n][n];
        
        //traversing & handling trivial cases and rest of the dp
        for(int gap = 0 ; gap <  n ; gap++){
            
            for(int i = 0 , j = gap ; j < n ; i++ , j++){
                
                //when only one coin
                if(gap == 0)
                dp[i][j] = arr[i];  //i==j
                
                //when only 2 coin, you take maximum of 2
                else if(gap == 1)
                dp[i][j] = Math.max(arr[i],arr[j]);
                
                //when more than 2 coins
                else{
                    /* if you chose ith coin , the opponent will choose the next coin
                    such that you get minimum of next choice
                    */
                    int cost1 = arr[i] + Math.min(dp[i+2][j],dp[i+1][j-1]);
                    
                    /* if you chose ith coin , the opponent will choose the next coin
                    such that you get minimum of next choice
                    */
                    
                    int cost2 = arr[j] + Math.min(dp[i+1][j-1] , dp[i][j-2]);
                    
                    
                    //but you will make choices such that you get max of cost1 and cost2
                    dp[i][j] = Math.max(cost1 , cost2);
                }
            }
        }
        
        return dp[0][n-1];
        //returning answer
    }
}
  
  
  
  
  
  
  
  
  
  
  

//{ Driver Code Starts
//Initial Template for Java

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
	public static void main(String[] args) throws IOException
	{
	        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));
        int t =
            Integer.parseInt(br.readLine().trim()); // Inputting the testcases
        while(t-->0)
        {
            long n = Long.parseLong(br.readLine().trim());
            long a[] = new long[(int)(n)];
            // long getAnswer[] = new long[(int)(n)];
            String inputLine[] = br.readLine().trim().split(" ");
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(inputLine[i]);
            }
            long k = Long.parseLong(br.readLine().trim());
            
            Compute obj = new Compute();
            System.out.println(obj.maxSumWithK(a, n, k));
            
        }
	}
}


// } Driver Code Ends


//User function Template for Java


class Compute {
    
    public long maxSumWithK(long arr[], long n, long k)
    {
        //applying kadanes and storing answers
        long msa[] = new long[arr.length];
        msa[0] = arr[0];
        long csum = arr[0]; 
        for(int i = 1 ; i < arr.length ; i++){
            
            if(csum > 0)
            csum += arr[i];
            
            else
            csum = arr[i];
            
            msa[i] = csum;
        }
        
        // for(int i = 0 ; i < arr.length ; i++)
        // System.out.print(msa[i] + " ");
        
        // System.out.println();
        
        //finding ans of first window
        long exactK = 0 , ans = Integer.MIN_VALUE;
        
        for(int i = 0 ; i < (int)k ; i++)
        exactK += arr[i];
        
        ans = Math.max(ans , exactK);
        //moving the window through rest of the array 
        
        for(int j = (int)k; j < arr.length ; j++){
            
            exactK += arr[j] - arr[j - (int)k];
            
            long atleastK = exactK + msa[j- (int)k];
            
            ans = Math.max(ans , exactK);
            ans = Math.max(ans , atleastK);
        }
        //returning answer
        return ans;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        //kadane's algorithm will be used to find maximum subarray
        
        //current sum , overall max subarray
        int csum = nums[0] , omax = nums[0] , n = nums.length;

        for(int i =1 ; i < n ; i++){
            
            int value = nums[i];

            //if previous train is +ve jump into it 
            if(csum >= 0)
            csum += value;

            //else start your own
            else
            csum = value;

            //update max
            omax = Math.max(omax , csum);
        }

        return omax;
    }
}

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;
class GfG
{
    public static void main(String args[])
        {
            Scanner sc = new Scanner(System.in);
            int t = sc.nextInt();
            while(t-->0)
                {
                    String X = sc.next();
                    String Y = sc.next();
                    int costX = sc.nextInt();
                    int costY = sc.nextInt();
                    
                   
                    Solution ob = new Solution();
                    System.out.println(ob.findMinCost(X,Y,costX,costY));
                }
        }
}    
// } Driver Code Ends


//User function Template for Java

class Solution
{
	public int findMinCost(String s1, String s2, int costX, int costY)
	{
		//similiar to Leetcode 712, minimum cost(MC)
 
        //every cell will store MC for ith string to be equal to jth string
 
        int m = s1.length() , n = s2.length();
        int[][] dp = new int[m+1][n+1];     //+1 for empty string
 
        //last row and last col will be 0
        
        for(int i = m; i>=0 ;i--){
 
            for(int j = n ; j>=0 ; j--){
                
                //last cell
                if(i == m && j == n)
                dp[i][j] = 0;
                
                //last col , we will have to delete all chars to match "-"
                else if(j == n)
                dp[i][j] = dp[i+1][j] + costX;
 
                //last row , we will have to delete all chars to match "-"
                else if(i == m)
                dp[i][j] = dp[i][j+1] + costY;
 
                //ROD - rest of the dp
                else{
                    //if chars are equal check diagonally forward
                    if(s1.charAt(i) == s2.charAt(j))
                    dp[i][j] = dp[i+1][j+1];
                    
                    /*removing first char of str1 and checking MC with ros str2
                    and vice versa ...and also removing both and checking
                    diagonally....and taking minimum of all and adding the
                    the cost value of character removed
                    */
                    else{
                        int MC1 = dp[i+1][j] + costX;
                        int MC2 = dp[i][j+1] + costY;
                        int MC3 = dp[i+1][j+1] + costX + costY;
                        dp[i][j] = Math.min(MC1 , Math.min(MC2,MC3));
                    }
                }
            }
        }
 
        return dp[0][0];
	}
}

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        //Ques 40 of dp playlist ,minimum ASCCII SUM (MAS)

        //every cell will store MAS for ith string to be equal to jth string

        int m = s1.length() , n = s2.length();
        int[][] dp = new int[m+1][n+1];     //+1 for empty string

        //last row and last col will be 0
        
        for(int i = m; i>=0 ;i--){

            for(int j = n ; j>=0 ; j--){
                
                //last cell
                if(i == m && j == n)
                dp[i][j] = 0;
                
                //last col, it will be down cell + ASCII of current character
                else if(j == n)
                dp[i][j] = dp[i+1][j] + (int)s1.charAt(i);

                //last row, it will be right cell + ASCII of current character
                else if(i == m)
                dp[i][j] = dp[i][j+1] + (int)s2.charAt(j);

                //ROD - rest of the dp
                else{
                    if(s1.charAt(i) == s2.charAt(j))
                    dp[i][j] = dp[i+1][j+1];
                    
                    /*removing first char of str1 and checking MAS with ros str2
                    and vice versa ...and taking minimum of both while adding
                    the ascii value of character removed
                    */
                    else{
                        int MAS1 = dp[i+1][j] + (int)(s1.charAt(i));
                        int MAS2 = dp[i][j+1] + (int)(s2.charAt(j));
                        dp[i][j] = Math.min(MAS1 , MAS2);
                    }
                }
            }
        }

        return dp[0][0];
    }
}

class Solution {
    public boolean isScramble(String s1, String s2) {
        /* DP ques 39 
        */
        //if lengths are not equal return false
        if(s1.length() != s2.length())
        return false;

        int n = s1.length();

        //making 3d dp putting s1 on row ,s2 on col and length+1 on z axis
        boolean[][][] dp = new boolean[n][n][n+1];

        //traversing the dp

        for(int len = 1 ; len <= n ; len++){

            for(int i = 0 ; i <= n-len ; i++){

                for(int j = 0 ; j <= n - len ; j++){
                    
                    // for len 1 if chars are not equal -> false else true
                    if(len == 1)
                    dp[i][j][len] = (s1.charAt(i) == s2.charAt(j));

                    else{

                        /* making cuts on strings , and looping till either all
                        cuts have been covered or we have already found true
                        */
                        for(int k = 1 ; k < len && !dp[i][j][len];k++){
                            dp[i][j][len] = 
                            
                            //left-left             right-right
                            (dp[i][j][k] && dp[i+k][j+k][len-k]) ||
                            
                            //left - right          right - left
                            (dp[i][j+len-k][k] && dp[i+k][j][len-k]);
                        }
                    }
                }
            }
        }

        

        return dp[0][0][n];
    }
    
    //recursion 1 , recursion 2 and recursion with memoization
    // public boolean isScramble1(String s1, String s2){
    //     if(s1.equals(s2))
    //     return true;

    //     for(int i = 1 ; i < s1.length() ; i++){

    //         if(isScramble1(s1.substring(0,i),s2.substring(0,i)) && isScramble1(s1.substring(i),s2.substring(i)))) ||
    //         (isScramble1(s1.substring(0,i),s2.substring(s2.length()-i)) && isScramble1(s1.substring(i),s2.substring(0,s2.length()-i))) )
    //         return true;
    //     }
    //     return false;
    // }
    // public boolean isScramble2(String s1, String s2 , int si1 ,int ei1 , int si2 , int ei2){
    //     if(s1.equals(s2))
    //     return true;

    //     for(int i = 1 ; i < s1.length() ; i++){

    //         if( (isScramble2(s1,s2,si1,si1+i,si2,si2+i) && isScramble2(s1,s2,si1+i + 1,ei1,si2+i+1,ei2)) ||
    //         (isScramble2(s1,s2,si1,si1+i,ei2-1,ei2) && isScramble2(s1,s2,si1,si1+i+1,ei1,ei2-i-1)) )
    //         return true;
    //     }
    //     return false;

    // }
    // public boolean isScramble3(String s1, String s2 ,int si1, int si2 , int len , Boolean[][][] dp){
    //     if(s1.substring(si1,si1+len).equals(s2.substring(si2,si2+len)))
    //     return true;
        
    //     if(dp[si1][si2][len] != null)
    //     return dp[si1][si2][len];

    //     for(int k = 1 ; k<len ; k++){
    //         if((isScramble3(s1,s2,si1,si2,k,dp) && isScramble3(s1,s2,si1+k,si2+k,len-k,dp)) ||
    //         (isScramble3(s1,s2,si1,si2+len-k,k,dp) && isScramble3(s1,s2,si1+k,si2,len-k,dp))){
    //             dp[si1][si2][len];
    //             return true;
    //         }
            
    //     }
        
    //     dp[si1][si2][len] = false;
    //     return false;
    // }





}     

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length() , n = word2.length();

        int dp[][] = new int [m+1][n+1];

        /* every cell stores minimum cost needed to convert string till that row to
        string till that coloumn 
        */
        
        //base case filling first row and coloumn
        for(int j = 0 ; j < dp[0].length ; j++)
        dp[0][j] = j;

        for(int i = 0 ; i < dp.length ; i++)
        dp[i][0] = i;


        for(int i = 1 ; i < dp.length ; i++){

            for(int j = 1 ; j < dp[0].length ;j++){

                if(word1.charAt(i-1) == word2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];

                else{
                    //replace
                    int replace = dp[i-1][j-1];
                    
                    //delete
                    int delete = dp[i-1][j];
                    
                    //insert
                    int insert = dp[i][j-1];

                    //find min and add 1 for your own operation
                    dp[i][j] = Math.min(replace ,Math.min(delete , insert)) +1;
                }
            }
        }

        return dp[m][n];
    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        //Q37 of dp playlist ,

        int m = p.length() , n = s.length();   //pattern on rows , str on col
        boolean [][] dp = new boolean[m+1][n+1];    //for empty string

        //traversing the dp
        for(int i = 0 ; i < m+1 ; i++){

            for(int j = 0 ; j< n+1 ; j++){

                //if 0,0 ->true
                if(i == 0 && j== 0)
                dp[i][j] = true;

                //if first coloumn
                else if(j==0){
                    
                    //if * check 2 rows above
                    if(p.charAt(i-1) == '*')
                    dp[i][j] = dp[i-2][j];

                    //if p.charAt(j) == any char or '.' it stays false
                }

                //first row all false
                else if(i==0)
                dp[i][j] = false;

                //rest of the string
                else{
                    
                    //if chars are equal or . then check diagonally behind
                    if(p.charAt(i-1)==s.charAt(j-1) || p.charAt(i-1) == '.')
                    dp[i][j] = dp[i-1][j-1];

                    /* if * then check 2 rows above and also if last chars
                    are equal then check left also , ans will be OR of both

                    here last chars means char before * and last char of str
                    char before * can also be '.'
                    */
                    else if(p.charAt(i-1) == '*'){
                        dp[i][j] = dp[i-2][j]; 
                        
                        if(p.charAt(i-2)==s.charAt(j-1) || p.charAt(i-2) == '.')
                        dp[i][j] = dp[i][j] || dp[i][j-1];
                    }
                }
            }
        }

        // for(int i = 0 ; i < m+1 ; i++){
        //     for(int j = 0 ; j < n+1 ; j++)
        //     System.out.print(dp[i][j] + " ");

        //     System.out.println();
        // }

        return dp[m][n];
    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        //Ques 36 , dp playlist
        
        int m = p.length() , n = s.length();
        boolean dp[][] = new boolean[m+1][n+1]; //+1 for empty string

    //last cell will be true , else last row and last colomn will be false
        
        //traversing reversely
        for(int i = m ; i >=0 ; i--){

            for(int j = n ; j>=0 ; j--){

                //if last cell
                if(i == m && j== n)
                dp[i][j] = true;

                //if last row
                else if(i == m)
                dp[i][j] = false;

                //if last coloumn
                else if(j == n){
                    //and * check below 
                    if(p.charAt(i) == '*')
                    dp[i][j] = dp[i+1][j];

                    //else outright false
                    else
                    dp[i][j] = false;
                }

                //for rest of the matrix
                else{
                    
                    //if ? , or char are same then check diagonally right
                    //else it stays false , which is by default
                    if(p.charAt(i) == '?' || p.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j+1];

                    //if * in rest of the matrix check right and below
                    else if(p.charAt(i) == '*')
                    dp[i][j] = dp[i][j+1] || dp[i+1][j];
                }
                
            }
        }

        // for(int i =0 ; i < m+1 ; i++){
        //     for(int j = 0 ; j < n+1 ; j++)
        //     System.out.print(dp[i][j] + " ");

        //     System.out.println();
        // }
        return dp[0][0];
    }
}

//{ Driver Code Starts
//Initial Template for Java

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while(T-->0)
        {
            String str = br.readLine().trim();
            Solution ob = new Solution();
            int ans = ob.LongestRepeatingSubsequence(str);
            System.out.println(ans);
        }
    }
}

// } Driver Code Ends


//User function Template for Java

class Solution
{
    public int LongestRepeatingSubsequence(String str)
    {   
        /* Q35 dp playlist , finding Longest common subsequence in str with itself ,
        and checking if equal characters have equal indexes or not as we need to find
        repeated string with different characters
        */
        int n = str.length() ;
        
        int[][] dp = new int[n+1][n+1];
        
        //last row ,last coloumn  and last cell will be 0 by default
        //handling for rest of the dp
        for(int i = n-1 ; i>=0 ; i--){
            
            for(int j = n-1 ; j>=0 ; j--){
                
                //checking if chars are equal and indexes are not
                if(str.charAt(i) == str.charAt(j) && i!=j)
                    dp[i][j] = dp[i+1][j+1] + 1;
            
                else
                    dp[i][j] = Math.max(dp[i][j+1] , dp[i+1][j]);
            
            }
        }
        
        return dp[0][0];
    }
}

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;

class GFG
{
    public static void main(String args[])throws IOException
    {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(read.readLine());
        while(t-- > 0)
        {
            String input[] = read.readLine().trim().split(" ");
            int n = Integer.parseInt(input[0]);
            int m = Integer.parseInt(input[1]);
            
            String S1 = read.readLine().trim();
            String S2 = read.readLine().trim();

            Solution ob = new Solution();
            System.out.println(ob.longestCommonSubstr(S1, S2, n, m));
        }
    }
}
// } Driver Code Ends


//User function Template for Java

class Solution{
    int longestCommonSubstr(String s1, String s2, int m, int n){
        /* Q34 of dp playlist , compare all prefixes of both s1 and s2 and find longest
        common suffix , that will become your longest common substring
        */
        
        int dp[][] = new int[m+1][n+1];
        int ans = 0;
        
        //first coloumn and first row will be 0 , which is by default also 0
        
        for(int i = 1 ; i < m+1 ; i++){
            
            for(int j = 1 ; j < n+1; j++){
                
                //if last chars are equal , ans = ansof(prefix) + 1 , ans of prefix
                //can be found diagonally behind
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ans = Math.max(ans , dp[i][j]);
                }
                
            }
        }
        
        // for(int i = 0 ; i < m ; i++){
        //     for(int j = 0 ; j<n ; j++){
        //         System.out.print(dp[i][j] + " ");
        //     }
        //     System.out.println();
        // }
        
        return ans;
    }
}

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;

class GFG {
    public static void main(String args[]) throws IOException {
        BufferedReader read =
            new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(read.readLine());
        while (t-- > 0) {
            String s = read.readLine();
            Solution ob = new Solution();
            System.out.println(ob.distinctSubsequences(s));
        }
    }
}
// } Driver Code Ends


//User function Template for Java

class Solution {
    int distinctSubsequences(String s) {
        //not getting submitted on GFG cause not included mod operations
        //every cell denotes no. of distinct subsequences(NODS) till that string
        
        int n = s.length();
        
        //n+1 , as 0th place would be taken by empty subsequence
        int dp[] = new int[n+1];    
        dp[0] = 1 ;//for 1 character string , NODS = 1
        
        //make HM to store latest indexes of repeated characters
        HashMap<Character ,Integer> map = new HashMap<>();
        
        for(int i = 1 ; i < n+1 ; i++){
            
            dp[i] = 2*dp[i-1];
            
            char ch = s.charAt(i-1);  //dp is 1 greater than string
            
            /* if character already exists means its repeated, so we will subtract all
            subsequences of dp[ch - 1] where ch represent last occurence of repeated 
            character before now, as those are the ones which will get combined and repeated
            */
            if(map.containsKey(ch)) {
                int idx = map.get(ch);  //getting previous occurence of repeated character
                dp[i] -= dp[idx- 1];
            }
            
            map.put(ch , i);    //updating characters
        }
        
        return dp[n];
    }
}

class Solution {
    public String longestPalindrome(String s) {
        /*  Q30 dp playlist , similiar to Q22 
            the last true cell will be the LPS with length gap +1 
            which can be found by substring(i , j+1)
        */
        //making 2d dp
        int n = s.length();
        String ans = "";
        boolean dp[][] = new boolean[n][n];

        for(int gap = 0 ; gap < n ; gap ++){

            for(int i = 0 , j = gap ; j < n ;i++, j++){

                if(gap == 0 )
                    dp[i][j] = true;

                else if(gap == 1)
                    dp[i][j] = s.charAt(i)==s.charAt(j) ? true : false;
                    
                else{
                    if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1];

                    //else default value is already false
                }

                //storing the substring of the last true value
                if(dp[i][j] == true) 
                ans = s.substring(i,j+1);
            }
        }

        return ans;
    }
}

//{ Driver Code Starts
import java.util.*;
class GFG
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		sc.nextLine();
		while(t>0)
		{
			String str = sc.nextLine();
			//System.out.println(str.length());
			Solution ob  = new Solution();
			System.out.println(ob.countPS(str));
		t--;
		}
	}
}
// } Driver Code Ends


/*You are required to complete below method */

class Solution
{
    long countPS(String s)
    {
        //making 2d dp array, S&m - every cell denotes LPS of that string
        long mod = 1000000000 + 7;
        int n = s.length();
        long[][] dp = new long[n][n];

        for(int gap = 0 ; gap < n ; gap++){
                
            for(int i = 0 , j = gap; j < n ; i++ , j++){
                if(gap == 0)
                dp[i][j] = 1;   //for 1 character string CPS = 1

                //for 2char string , CPS = 3 if c1=c2 else CPS = 2
                else if(gap == 1)
                dp[i][j] = s.charAt(i)==s.charAt(j) ? 3 : 2;
                

                //i denotes prefix , j denotes suffix
                else{
                    
                    //if c1 == c2 , CPS of prefix + suffix + 1 (for c1+empty subsequence+c2)
                    if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = 1 + dp[i][j-1]  + dp[i+1][j] ;

                    //else CPS of suffix + prefix - middlepart
                    else
                    dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
                }
            }
        }

        // for(int i = 0 ; i < n ; i++){
        //     for(int j =  0 ; j < n ;j++)
        //     System.out.print(dp[i][j] + " ");

        //     System.out.println();
        // }
        

        return dp[0][n-1] ;

    }
}

class Solution {
    public int longestPalindromeSubseq(String s) {
        /* Q29 of dp series , gap1 strategy 
        */

        //making 2d dp array, S&m - every cell denotes LPS of that string
        int n = s.length();
        int[][] dp = new int[n][n];

        for(int gap = 0 ; gap < n ; gap++){
                
            for(int i = 0 , j = gap; j < n ; i++ , j++){
                if(gap == 0)
                dp[i][j] = 1;   //for 1 character string LPS = 1

                //for 2char string , LPS = 2 if c1=c2 else LPS = 1
                else if(gap == 1)
                dp[i][j] = s.charAt(i)==s.charAt(j) ? 2 : 1;
                

                //i denotes prefix , j denotes suffix
                else{
                    
                    //if c1 == c2 , LCS of middle part + 2 for both chars
                    if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1] + 2;

                    //else max of (prefix , suffix)
                    else
                    dp[i][j] = Math.max(dp[i][j-1] , dp[i+1][j]);
                }
            }
        }

        // for(int i = 0 ; i < n ; i++){
        //     for(int j =  0 ; j < n ;j++)
        //     System.out.print(dp[i][j] + " ");

        //     System.out.println();
        // }
        

        return dp[0][n-1];
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        /* Q28 dp playlist , every cell denotes LCS for that coloumn string
        with that row string 

        2)smallest problem on bottom left , biggest problem on 0,0
        
        3)making 2d dp array , keeping text 1 on coloumn and text2 on row +1
        for dash or empty string

        */

        int m = text1.length() , n = text2.length();
        int[][] dp = new int[m+1][n+1];

        //last coloumn , last row will be 0 for dashes
        // i represent text1 , j represent text2
        for(int i = m-1 ; i>= 0 ; i--){

            for(int j = n-1 ; j>=0 ; j--){
                
                //if first chars are equal , diagonally right +1 will be ans
                if(text1.charAt(i) == text2.charAt(j))
                dp[i][j] = dp[i+1][j+1] + 1;

                //else max (horizontal ,vertical) will be answer
                else
                dp[i][j] = Math.max(dp[i+1][j] , dp[i][j+1]);
            }
        }

        return dp[0][0];
    }
}

class Solution {
    public int minScoreTriangulation(int[] values) {
        /*  question no 27 in notes of dp playlist , catalan number , gap 
        strategy and matrix chain multiplication are being used 

        1) make 2d dp array to store results of previous polygon 
        2)every cell denotes minimum score to make that polygon with that 
        many sides
        3) traversing the gap diagnols and handling trivial cases  0 , 1

        4) handling further gap diagonals through formula for left , right 
        and immediate triangle using gap strategy 2
        */

        int n = values.length;
        int[][] dp = new int[n][n];

        for(int gap = 0 ; gap < n ; gap ++){

            for(int i = 0 , j = gap ; j < n ; i++ , j++){

                if(gap == 0 )
                dp[i][j] = 0;
                
                else if(gap == 1)
                dp[i][j] = 0;

                //only 1 triangle can be formed with 3 points
                else if(gap == 2)
                dp[i][j] = values[i] * values[i+1] * values[i+2];

                else{
                    //4
                    int min = Integer.MAX_VALUE;
                    for(int k = i+1 ; k<= j-1 ; k++){
                        int left = dp[i][k];
                        int right = dp[k][j];
                        int triangle = values[i] * values[j] * values[k];

                        min = Math.min(min , left + right + triangle);
                    }

                    dp[i][j] = min;
                }
            }
        }

        return dp[0][n-1];
    }
} 

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;

class GFG{
    public static void main(String args[])throws IOException
    {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(read.readLine());
        while(t-- > 0)
        {
            int n = Integer.parseInt(read.readLine());
            String input_line[] = read.readLine().trim().split("\\s+");
            int keys[]= new int[n];
            for(int i = 0; i < n; i++)
                keys[i] = Integer.parseInt(input_line[i]);
            String input_line1[] = read.readLine().trim().split("\\s+");
            int freq[]= new int[n];
            for(int i = 0; i < n; i++)
                freq[i] = Integer.parseInt(input_line1[i]);
            Solution ob = new Solution();
            System.out.println(ob.optimalSearchTree(keys, freq, n));
        }
    }
}
// } Driver Code Ends


//User function Template for Java

class Solution
{
    static int optimalSearchTree(int keys[], int frequency[], int n)
    {
        //making 2d dp for gap strategy
        int[][] dp = new int[n][n];
        
        //making prefix sum array
        int psa[] = new int[n] , sum = 0;
        
        for(int i = 0 ; i < n ; i++){
            sum += frequency[i];
            psa[i] = sum;
        }
        
        for(int gap = 0 ; gap < n ; gap ++){
            
            //traversing on gap diagnols
            for(int i = 0 , j = gap ; j < n ;i++, j++){
                
                if(gap == 0)
                dp[i][j] = frequency[i];     //i == j
                
                else if(gap == 1){
                    //i = left node , j = right node
                    int f1 = frequency[i] , f2 = frequency[j];
                    dp[i][j] = Math.min(f1 + 2*f2 , 2*f1 + f2);
                }
                
                else{
                    //freq to be added with left and right
                    int freq =0;
                    // for(int x = i ; x <= j ; x++)
                    // freq += frequency[x];
                    
                    //can also be done through prefix sum array for optimization
                    freq = psa[j] - (i == 0 ? 0 : psa[i-1]);
                    //i = left side , j = right side
                    int min = Integer.MAX_VALUE;
                    for(int k = i ; k <= j ;k++){
                        
                        //if k is at begning it left will be zero and if at end righ will
                        // be zero 
                        int left = k == i ? 0 : dp[i][k-1];
                        int right = k == j ? 0 : dp[k+1][j];
                        
                        min = Math.min(min , left + right + freq);
                    }
                    
                    dp[i][j] = min;
                }
            }
        }
        
        return dp[0][n-1];
    }
}

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;

class GFG
{
    public static void main(String args[])throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        while(t-- > 0){
            int N = Integer.parseInt(in.readLine());
            String input_line[] = in.readLine().trim().split("\\s+");
            int arr[]= new int[N];
            for(int i = 0; i < N; i++)
                arr[i] = Integer.parseInt(input_line[i]);
            
            Solution ob = new Solution();
            System.out.println(ob.matrixMultiplication(N, arr));
        }
    }
}

// } Driver Code Ends


//User function Template for Java

class Solution{
    static int matrixMultiplication(int n, int arr[])
    {
        /* making a dp array for the gap strategy and to store answer of previous matrice
        multiplication
        1)travelling the gap diagonals and handling trivial cases for 0 and 1 diagnol
        2)handling for gap diagonals >= 2
        */
        
        int[][] dp = new int[n-1][n-1];
        
        //1
        for(int gap = 0 ; gap < n-1 ; gap++ ){
            
            
            for(int i =0 , j = gap ; j < n-1 ; i++ ,j++){
                
                if(gap == 0)
                dp[i][j] = 0;
                
                //i is first matrix , j is 2nd matrix
                else if(gap == 1)
                dp[i][j] = arr[i] * arr[j] * arr[j+1];
                
                //2
                else{
                    //k represents the cuts we are making from 0 to j-1
                    
                    int min = Integer.MAX_VALUE;
                    for(int k = i ; k < j ; k++){
                    //dp -> [i,k] = left half and [k+1,j] = right half
                    //arr -> i*k+1 = left half , k+1*j+1 = right half
                        int left = dp[i][k];
                        int right = dp[k+1][j];
                        int m = arr[i] * arr[k+1] * arr[j+1];
                        
                        min = Math.min(min , left + right + m);
                    }
                    dp[i][j] = min;
                }
            }
        }
        
        return dp[0][n-2];
    }
}

class Solution {
    public int minCut(String s) {
        /* dp playlist video 28 , 2nd approach O(n^2)
        */

        //make boolean 2d array
        int n = s.length();
        boolean[][] arr = new boolean[n][n];

        
        //traversing diagonally up
        for(int gap = 0 ; gap < n ; gap++){

            for(int i = 0 , j = gap ; j < n ; i++ , j++){

                if(gap == 0)
                arr[i][j] = true;

                else if(gap == 1){
                    if(s.charAt(i) == s.charAt(j)) 
                    arr[i][j] = true;
                }
                

                else{
                    if(s.charAt(i) == s.charAt(j) && arr[i+1][j-1]==true)
                    arr[i][j] = true;
                }
                
            }
        }

        //making 1d dp array 
        int dp[] = new int [n];
        dp[0] = 0;  //0 letters need no cuts
        
        //now checking every suffix from 
        for(int i = 1 ; i < n ; i++){
            
            int min = Integer.MAX_VALUE;
            //making suffix and checking from boolean table
            for(int j = i ; j >= 0 ;j-- ){
                //if suffix is already a pallindrome
                if(j==0 && arr[j][i])
                min = 0;

                else if(arr[j][i])
                min = Math.min(min , dp[j-1] + 1);
            
            }
            dp[i] = min;

        }

        return dp[n-1];
    }
}

class Solution {
    public int minCut(String s) {
        /* dp playlist video 28 , first approach O(n^3)
        */

        //make boolean 2d array
        int n = s.length();
        boolean[][] arr = new boolean[n][n];

        
        //traversing diagonally up
        for(int gap = 0 ; gap < n ; gap++){

            for(int i = 0 , j = gap ; j < n ; i++ , j++){

                if(gap == 0)
                arr[i][j] = true;

                else if(gap == 1){
                    if(s.charAt(i) == s.charAt(j)) 
                    arr[i][j] = true;
                }
                

                else{
                    if(s.charAt(i) == s.charAt(j) && arr[i+1][j-1]==true)
                    arr[i][j] = true;
                }
                
            }
        }

        //now making int 2d array to store minimum cuts on every cell
        int [][] dp = new int[n][n];

        for(int gap = 0 ; gap < n ; gap++){

            for(int i = 0 , j = gap ; j < n ; i++ , j++){
                //handling trivial cases
                if(gap == 0)
                dp[i][j] = 0;

                else if(gap == 1){
                    if(s.charAt(i) != s.charAt(j))
                    dp[i][j] = 1;
                }
                    
                
                

                else{
                    //if word is already a pallindrome
                    if(arr[i][j] == true)
                    dp[i][j] = 0;
                    
                    else{
                        /* now checking every partion call for minimum
                        cuts(faith) left string will be [i , k]  
                        right will be [k+1 , j] find minimum cut faith call
                        */
                        int min = Integer.MAX_VALUE;
                        //k starts from i and ends on j
                        for(int k = i ; k < j ;k++){
                            int left = dp[i][k];
                            int right = dp[k+1][j];

                            min = Math.min(min,left + right);
                        }

                        dp[i][j] = min +1;  //add 1 for faith call

                        }
                }
            }
        }
        return dp[0][n-1];  //last coloumn of first row will have answer
    }
}

class Solution {
    public int countSubstrings(String s) {
        /* question of DP gap strategy vid 32 of dp playlist
        
        1)making a boolean array for checking pallindrome by keeping start
        points on coloumn and end points on rows
        
        2)travelling the upper triangle only ,where 0th diagnol represents
        substring with 0 gap that is that element itself 

        3) handling for 0 ,1 gap which are trivial case then handling for 
        2 onwards , where we will check extremities and if inside string is 
        also pallindrome by checking diagnolly behind
        */

        //1
        boolean dp[][] = new boolean[s.length()][s.length()];
        int count = 0 , n = s.length();

        //2

        for(int gap = 0 ; gap < n ; gap ++){
            
            //every diagnol ends at last coloumn,so this loop runs from first
            //row till last coloumn
            for(int i = 0 , j = gap ; j < n ; i++ , j++){

                //handling for 0 gap diagnol -> all are true
                if(gap == 0 ){
                    dp[i][j] = true;
                    count++;
                }
                


                //handling for 1 gap diagnol -> check if both chars are equal
                else if(gap == 1){
                    if(s.charAt(i) == s.charAt(j)){
                        dp[i][j] = true;
                        count++;
                    }
                    
                }


                //3
                else{
                    
                    if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == true){
                        dp[i][j] = true;
                        count++;
                    }
                    
                }
            }
        }

        return count;
        
    }
}

//{ Driver Code Starts
import java.io.*;
import java.util.*;

class RodCutting {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

            Solution ob = new Solution();
            System.out.println(ob.cutRod(arr, n));
        }
    }
}

// } Driver Code Ends


class Solution{
    public int cutRod(int price[], int n) {
        /* storage and meaning - every cell denotes maximum profit if the rod had been of
        that length 
        */
        
        int dp[] = new int[n+1];
        int nprice[] = new int[n+1];  //for ease of indexing
        
        //copying all prices in 1 based indexing
        for(int i = 1 ; i < n+1 ; i++)
        nprice[i] = price[i-1];
        
        //dp of 0 is already 0 
        dp[1] = nprice[1];  //1 length of rod can only be sold for price of 1 length
        
        
        for(int i = 2 ; i < n+1 ; i++){
            
            //storing profit when rod is not cut at all and sold at full length of i only
            int maxProfit = nprice[i]; 
            
            //cutting rod in 1 to i-1 pieces and checking for max profit 
          //with optimized i-j 
            for(int j = 1 ;j < i ; j++ )
            maxProfit = Math.max(maxProfit , dp[i-j] + nprice[j]);
          
          //or 
          //this will be cutting in j and taking cartesian product of optimized j & 
         //optimized i-j , we only have to travel till half as then pairs will get repeated
			// for(int j = 1 ;j <= i/2 ; j++ )
            // maxProfit = Math.max(maxProfit , dp[i-j] + dp[j]);
                
            dp[i] = maxProfit;
            
        }
        
        // for(int i = 0 ; i < n+1 ; i ++)
        // System.out.print(dp[i] + " ");
        
        return dp[n];
    }
}

public class Solution {
    public int chordCnt(int n) {
        long mod = 1000000000 + 7;
        long dp[] = new long[n+1];
        dp[0] = 1 ; dp[1] = 1;
        
        for(int k = 2  ; k <= n ; k++){
            
            for(int i = 0 , j = k-1 ; i <= k-1 ; i++ , j--)
            dp[k]= (dp[k]%mod + (((dp[i]%mod)*(dp[j]%mod))%mod))%mod;
        }
        
        return (int)(dp[n] % mod);
    }
}

class Solution {
    public List<String> generateParenthesis(int n) {
        /* you can find how many total no. of brackets will be generated 
        through catalan number 

        TC for interview purposes - O(n * 2^2n)
        */

         backtrack("" , 0 , 0 , n);
         return res;
    }
    public List<String> res = new ArrayList<>();

    //open -> open brackets , clost brackets
    public void backtrack(String sb , int open , int close , int n){
        //base condition
        if(sb.length() == 2*n){
            res.add(sb);
            return;
        }

        //always start with open bracket
        if(open < n)
        backtrack(sb + "(", open + 1 , close , n);

        //close brackets should always be lesser than open,make recursion 
        //tree to understand this better
        if(close < open)
        backtrack(sb + ")",open ,close+1 , n);
    }
}

import java.io.*;
import java.util.*;

public class Main {

   public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      long[] dp = new long[n + 1];
      dp[0] = 1;

      for(int i = 1; i < dp.length; i++){
         for(int j = 0; j < i; j++){
            dp[i] += dp[j] * dp[i - 1 - j];
         }
      }

      System.out.println(dp[n]);
   }

}


                        


                        

class Solution {
    public int numTrees(int n) {
        /* basically a question of catalan number , learn the first 5 catalan
        numbers to be able to find the pattern in questions
        */

        int[] dp = new int[n+1];
        dp[0] = 1 ; dp[1] = 1;
        
        
        for(int k = 2 ; k <= n ; k++){

            for(int i = 0 , j = k-1 ; i<=k-1 ; i++ , j--)
            dp[k] += dp[i] * dp[j];
        }

        return dp[n];
    }
}

// // "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        System.out.println(findCatalan(8));
    }
    //Function to find the nth catalan number.
    public static int findCatalan(int n)
    {
        
        int dp[] = new int[n+1];
        dp[0] = 1 ; dp[1] = 1;
        
        for(int k = 2 ; k <= n; k++){
            
            for(int i = 0 , j = k-1 ; i <= k-1 ; i++ , j--){
                
                dp[k] += dp[i]*dp[j];
            }
        }
        
        return dp[n];
    }
}

class Solution {
    public int minScore(int n, int[][] roads) {
        /*question of connected components , find 1's component and find minimum edge 
        weight in 1's component as we have to find path between 1 and n
        */

        //making adjency list
        HashMap<Integer, ArrayList<List<Integer>>> map = new HashMap<>();

        for(int[] road : roads){

            map.computeIfAbsent(road[0],k -> new ArrayList<List<Integer>>()).add(Arrays.asList(road[1],road[2]));

            map.computeIfAbsent(road[1],k -> new ArrayList<List<Integer>>()).add(Arrays.asList(road[0],road[2]));
        }

        System.out.println(map);

        return BFS(n , map);
    }


    public int BFS(int n , HashMap<Integer, ArrayList<List<Integer>>> map){

        int ans = Integer.MAX_VALUE;
        Queue<Integer> q = new ArrayDeque<>();
        boolean visited[] = new boolean[n+1];
        
        //adding first node
        q.add(1);
        visited[1] = true;


        while(q.size()!=0){
            int node = q.poll();        //remove
            
            //work and then add into q
            //if(map.containsKey(node)==false) continue;

            for(List<Integer> edge : map.get(node)){
                ans = Math.min(ans , edge.get(1));

                if(visited[edge.get(0)]==false){
                    q.add(edge.get(0));
                    visited[edge.get(0)] = true;
                }
            }
            
        }

        return ans;
    }
}

class Solution {
    public int numSquares(int n) {
        /* dp solution , storage - 1d array , 
        meaning - every element will store minimum number of perfect squares it needs
         to sum to that element

            algo - solve left to right (smaller to larger)
        */

        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;

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

     //subtracting for all perfect squares smaller than i and finding previous answers
            int min = Integer.MAX_VALUE;
            for(int j = 1 ; j*j <= i ; j++){

                min = Math.min(min,dp[i - j*j]);
            }
            
            //adding 1 for subtracting current perfect square that is 
            // dp[i] = previous answer(dp[i - j*j]) + current(1 which is j*j)
            // if(min != Integer.MAX_VALUE)
            dp[i] = min +1;
        }

        return dp[n];
    }
}

class Solution {
    public class pair implements Comparable<pair>{
        int width , height ;

        pair(){

        }

        pair(int width , int height){
            this.width = width ; 
            this.height = height;
        }

        //this - other = ascending order , other-this = descending order
        public int compareTo(pair o){
            //if width are equal sort based on hieghts
            if(this.width == o.width)
            return this.height - o.height;

            //else sort based on width only
            else
            return this.width - o.width;
        }
    }
    public int maxEnvelopes(int[][] envelopes) {
        /* similiar to max overlapping bridges , LIS concept will be used here
        approach - sort on the bases of either width or height lets take width for eg:
        now you already have width in ascending order , 
        now find LIS of height for every width , maximum of these will be your answer 
        
        ** sorting width makes sure that you get width in ascending order and 
        finding LIS of heights makes sure no hieghts overlap to each other and you can 
        find Maximum LIS of heights which will become you answer
         */
        
        //making a pair class array to store heights and width of each envelops
        pair[] arr = new pair[envelopes.length];
         
         //taking input in the pair array
         int i = 0;
         for(int input[] : envelopes){    
            
            arr[i] = new pair();        //initializing the object
            arr[i].width = input[0];    
            arr[i].height = input[1];

            i++;
         }

         //sorting the pair array based on width
            Arrays.sort(arr);

         //calling LIS function based on height for all sorted widths in pair array

         return LIS(arr);
    }

    public int LIS(pair[] arr){
        int n = arr.length ;
        int[] LIS = new int[n];
        LIS[0] = 1;     //for the first envelop it can only make 1 LIS of envelopes
        
        int ans = 1;
        //traversing all the sorted widths envelops
        for(int i = 1 ; i < n ;i++ ){
            
            
         //checking all envelops before current which have smaller height and for those
         //which dont have their widths equal as it is mentioned in the question
            for(int j = i-1 ; j >= 0 ; j--){

                if(arr[j].width != arr[i].width && arr[j].height < arr[i].height)
                LIS[i] = Math.max(LIS[i],LIS[j]);
            }

            //adding LIS for current element
            LIS[i]+=1;

            ans = Math.max(ans , LIS[i]);
        }

        return ans;
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static class bridge implements Comparable<bridge>{
        int north , south ;
        
        bridge(){
            
        }
        bridge(int north ,int south){
            this.north = north;
            this.south = south;
        }
        
        //this - other = ascending order , other - this = descending
        public int compareTo(bridge o){
            
       //if north coordinates are equal sort in ascending order of south
            if(this.north == o.north)
            return this.south - o.north;
            
            //else sort in ascending order of north only
            else
            return this.north - o.north;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      bridge[] brdgs = new bridge[n];
      for (int i = 0; i < brdgs.length; i++) {
         String str = br.readLine();
         brdgs[i] = new bridge();
         brdgs[i].north = Integer.parseInt(str.split(" ")[0]);
         brdgs[i].south = Integer.parseInt(str.split(" ")[1]);
      }
      
      Arrays.sort(brdgs);   //sort in ascending order of north
      
      //now LIS based on south coordinate
      
      System.out.println(LIS(brdgs));
    }
    
    public static int LIS(bridge[] brdgs){
        int n= brdgs.length;
        int[] LIS = new int[n];
        
      //for first bridge it can only make 1 maximum non overlapping bridge
        LIS[0] = 1; 
        
        int ans = 1;
        for(int i = 1 ; i < n ; i++){
            
        //checking all bridges before current which have south coordinate         // smaller than current 
            for(int j = i-1 ; j >= 0 ; j--){
                if(brdgs[j].south < brdgs[i].south){
                    LIS[i] = Math.max(LIS[i],LIS[j]);
                }
            }
            LIS[i] += 1;    //adding length 1 for current bridge
            
            ans = Math.max(ans , LIS[i]);
        }
        
        return ans;
    }
    

}

//{ Driver Code Starts
//Initial Template for Java

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while(T-->0)
        {
            int n = Integer.parseInt(br.readLine().trim());
            String s = br.readLine().trim();
            String[] s1 = s.split(" ");
            int[] nums = new int[n];
            for(int i = 0; i < s1.length; i++)
                nums[i] = Integer.parseInt(s1[i]);
            Solution ob = new Solution();
            int ans = ob.LongestBitonicSequence(nums);
            System.out.println(ans);           
        }
    }
}

// } Driver Code Ends


//User function Template for Java

class Solution
{
    public int[] LIS(int[] nums ){
        int n = nums.length;
        
        int dp[] = new int[n];
        dp[0] = 1;  // for 1 length LIS will be 1 length
        
        for(int i = 1 ; i < n ; i++){
            
            for(int j = i-1 ; j>= 0 ; j--){
                
                //finding max in previous smaller elements
                if(nums[j] < nums[i])
                dp[i] = Math.max(dp[i] , dp[j]);
            }
            
            //adding +1 for current element
            dp[i] +=1;
            
        }
        
        return dp;
    }
    
    public int[] LDS(int[] nums){
        int n = nums.length;
        
        int dp[] = new int[n];
        dp[n-1] = 1;  // for 1 length LDS will be 1 length
        
        for(int i = n-2 ; i >=0 ; i--){
            
            for(int j = i+1 ; j< n ; j++){
                
                //finding max in previous smaller elements
                if(nums[j] < nums[i])
                dp[i] = Math.max(dp[i] , dp[j]);
            }
            
            //adding +1 for current element
            dp[i] +=1;
            
        }
        
        return dp;
    }
    public int LongestBitonicSequence(int[] nums)
    {
        /* for LBS we will need LIS and LDS , storage - 2 1D arrays for LIS and LDS
        meaning - 
        every cell will store LIS ending at that element this is going from left to right
        
        every cell will store LDS ending at that element this is going from right to left       
        
        LDS can be understood as LIS but in reverse array
        */ 
        
        int LIS[] = LIS(nums);
        
        //for LDS we can find reverse LIS 
        int LDS[] = LDS(nums);
        
        
        //now find max biotonic sequence for every element by LIS+LDS -1 and return max
        //-1 for the repeated element which exists in both LIS and LDS
        
        int ans = 0;
        for(int i = 0 ; i < nums.length ;i++){
            
            int biotonic = LIS[i] + LDS[i] -1;
            
            ans = Math.max(ans , biotonic);
        }
        
        return ans;
        
    }
}

//{ Driver Code Starts
//Initial Template for Java

import java.io.*;
import java.util.*;
class GfG
{
    public static void main(String args[])
        {
            Scanner sc = new Scanner(System.in);
            int t = sc.nextInt();
            while(t-->0)
                {
                    int n = sc.nextInt();
                    int Arr[] = new int[n];
                    for(int i = 0;i<n;i++)
                        Arr[i] = sc.nextInt();
                    Solution ob = new Solution();
                    System.out.println(ob.maxSumIS(Arr,n));
                }
        }
}    
// } Driver Code Ends


//User function Template for Java

class Solution
{
	public int maxSumIS(int arr[], int n)  
	{  
	        /* storage - 1d array , meaning - every cell will store maximum LIS sum ending at that
	    element(inclusive)
	    */
	    //base case
	    if(n == 1)return arr[0];
	    
	    int dp[] = new int[n];
	    dp[0] = arr[0]; //for length 1 max LIS will be that element
	    
	    int ans = dp[0];
	    
	    for(int i = 1 ; i< n ;i++){
	        
	        for(int j = i-1 ; j>= 0 ; j--){
//storing maximum LIS sum of previous elements provided the element is smaller than current
	            if(arr[j] < arr[i])
	            dp[i] = Math.max(dp[i],dp[j]);
	    }
	    //now adding current elements value to the max LIS
	    dp[i] += arr[i];
	    
	    ans = Math.max(dp[i],ans);
	}  
	
	return ans;
	}  
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    
    public static class Pair {
        int l;  //length
        int i;  //index
        int v;  //value
        String psf;
        
        Pair(int l, int i, int v, String psf){
            this.l = l;
            this.i = i;
            this.v = v;
            this.psf = psf;
        }
    }
        
    public static void solution(int []nums){
           /* 1D array
        storage- every cell denotes LIS till that cell ,mandatory that LIS ends at 
        that cell

        moving fromt left to right(small problem to large problem)
        */

        int n = nums.length;

        //base case
        // if(n == 1)return 1;
        int dp[] = new int[n];
        dp[0] = 1;  //LIS for 1 length will be of length 1 
        
        int ans = 1;
        for(int i = 1 ; i < n ; i++){

/*finding max LIS in previous elements in dp and also ensuring that current element
is greater than last element of previous LIS , as we have already assigned storage 
ensuring that LIS will end at that element so we already know that last element will 
be previous element only  */


            for(int j = i-1 ; j >=0 ; j--){
                
//for printing we are also taking equal values and not strictly
//greater values 
                if(nums[j] <= nums[i])
                dp[i] = Math.max(dp[i], dp[j]);
            }
            dp[i] += 1;

            ans = Math.max(dp[i] , ans);
        }        
        
/*we are returning ans and not dp[n-1] as dp[n-1] will just store LIS which the and 
will end at arr[n-1] but we need maximum length so we will store max as we traverse 
put in values in dp */

//now printing our answers through BFS for which we need pair class
        
        
        BFS(dp , ans , nums);

    }
    
    public static void BFS(int dp[] , int ans , int nums[]){
        
        ArrayDeque<Pair> q= new ArrayDeque<>();
        
        //add all elements which "ans" length stored in dp
        
        for(int i = 0 ; i < dp.length ; i++)
        if(dp[i]==ans)
        q.add(new Pair(dp[i],i,nums[i],nums[i]+""));
        
        
        //now remove print add children
        while(q.size()>0){
            Pair rem = q.removeFirst();
            
            int length = rem.l , idx = rem.i , val = rem.v;
            String psf = rem.psf;
            
            //if we got to LIS with 1 length print psf
            if(length ==1)
            System.out.println(psf);
            
//adding all children of rem which have length -1 and are smaller
            
            for(int j = 0 ; j < idx ; j++){
                
                if(dp[j]== length - 1 && nums[j] <= val)
                q.add(new Pair(dp[j],j,nums[j],nums[j]+" -> "+psf));   
            }
    
        }
    }
    
    
    
    public static void main(String []args){
        Scanner scn = new Scanner(System.in);

        int n = scn.nextInt();

        int arr[] = new int[n];
        for(int i = 0 ; i < n ; i++){
            arr[i] = scn.nextInt();
        }

        solution(arr);

        scn.close();
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        /* 1D array
        storage- every cell denotes LIS till that cell ,mandatory that LIS ends at 
        that cell

        moving fromt left to right(small problem to large problem)
        */

        int n = nums.length;

        //base case
        if(n == 1)return 1;
        int dp[] = new int[n];
        dp[0] = 1;  //LIS for 1 length will be of length 1 
        
        int ans = 1 ;
        for(int i = 1 ; i < n ; i++){

/*finding max LIS in previous elements in dp and also ensuring that current element
is greater than last element of previous LIS , as we have already assigned storage 
ensuring that LIS will end at that element so we already know that last element will 
be previous element only  */


            for(int j = i-1 ; j >=0 ; j--){
                
                if(nums[j] < nums[i])
                dp[i] = Math.max(dp[i], dp[j]);
            }
            dp[i] += 1;

            ans = Math.max(ans , dp[i]);
        }        
        return ans;
/*we are returning ans and not dp[n-1] as dp[n-1] will just store LIS which the and 
will end at arr[n-1] but we need maximum length so we will store max as we traverse 
put in values in dp */

    }
}

 class Solution {
    
    public int minSteps(int n) {
        // initialize the dp table
        int[] memo = new int[n + 1];
        memo[n] = 0;
        
        for (int i = n - 1; i >= 1; i--) {
            // since we want the minimum answer among all candidates, 
            // the result is initially set to the maximum value.
            int res = Integer.MAX_VALUE;

            // extra is the len of the copied string, 
            // nPastes is the number of paste operations performed after the initial copy.
            int len = i;
            int extra = len, nPastes = 0;

            // repeat while we can successfully paste the text
            while (len + extra <= n) {
                // paste the text
                len += extra;
                nPastes++;

                // find answer for the remaining length
                int remain = memo[len];

                // if answer is found, update the current result
                if (remain != -1)
                    res = Math.min(res, nPastes + remain);
            }

            // if answer is not found, return -1,
            // else return result + 1 (plus one to consider the copy operation we performed initially)
            memo[i] = res == Integer.MAX_VALUE ? -1 : res + 1;
        }
        
        return memo[1];
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static class pair {
        int i ;
        int j ;
        String psf;
        
        pair(int i , int j , String psf){
            this.i = i;
            this.j = j;
            this.psf = psf;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

        int[] val = new int[size];
        String str1 = br.readLine();
        for (int i = 0; i < size; i++) {
            val[i] = Integer.parseInt(str1.split(" ")[i]);
        }

        int[] wts = new int[size];
        String str2 = br.readLine();
        for (int i = 0; i < size; i++) {
            wts[i] = Integer.parseInt(str2.split(" ")[i]);
        }

        int cap = Integer.parseInt(br.readLine());

        //rows will be wts-val and cols will 0 to knapsack capacity (W)
         int dp[][] = new int[size+1][cap+1];
         int m = dp.length  , n = dp[0].length;
         
         //first row and first col will be 0 by default 
         
         //rest of the array
         
         for(int i = 1 ; i <m ;i++ ){
             for(int j = 1 ; j < n;j++){
                 
                 int plays = 0; 
                 int notplays = dp[i-1][j];
                 
                 if(j >= wts[i-1])
                 plays = val[i-1] + dp[i-1][j- wts[i-1]];
                 
                 dp[i][j] = Math.max(plays , notplays);
                 
             }
         }
         
         System.out.println(dp[m-1][n-1]);
         
         BFS(dp,val , wts);
        
    }
    
    public static void BFS(int[][]dp ,int[] val, int[] wts){
        ArrayDeque<pair> q = new ArrayDeque<>();
        q.add(new pair(dp.length -1 , dp[0].length-1,""));
        
        
        while(q.size()>0){
            pair rem = q.removeFirst();
            
            int i = rem.i , j = rem.j;
            String psf = rem.psf;
            
            //if players or balls become 0 print psf
            if(i == 0 || j == 0)
            System.out.println(psf);
            
            else{
                
                //when the number plays and when it doesn't play
                int plays = 0 , notplays = dp[i-1][j];
                
                if(j >= wts[i-1])
                plays= dp[i-1][j-wts[i-1]] + val[i-1];
                
                if(plays == dp[i][j])
                q.add(new pair(i-1 , j-wts[i-1] , i-1 +" "+psf));
                
                if(notplays == dp[i][j])
                q.add(new pair(i-1 , j , psf));
                
            }
        }
    }
}
















                        


                        


                        

import java.io.*;
import java.util.*;

public class Main {

    public static class Pair{
        int i;
        int j;
        String psf;

        public Pair(int i, int j, String psf){
            this.i = i;
            this.j = j;
            this.psf = psf;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        int[] arr = new int[size];

        for (int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int tar = Integer.parseInt(br.readLine());

        boolean dp[][] = new boolean[arr.length +1][tar+1];
        int m = dp.length , n = dp[0].length;
        
        
        //first col will be true
        for(int i = 0 ; i <m ;i++)
        dp[i][0] = true;
        
        //first row after first element will be false ,default in boolean 
        
        for(int i = 1 ; i < m ; i++){
            
            for(int j = 1 ; j < n ;j++){
                
    //number will contribute only if it is >= current col target
                if(j >= arr[i-1] ){
                    
                    if(dp[i-1][j] || dp[i][j- arr[i-1]])
                    dp[i][j] = true;
                }
                
            //else previous answer will be stored
                else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        System.out.println(dp[arr.length][tar]);
        
        BFS(dp ,arr, tar);

    }
    
    public static void BFS(boolean[][] dp,int[] arr ,int target ){
        
        ArrayDeque<Pair> q = new ArrayDeque<>();
    
        q.add(new Pair(arr.length,target , ""));
        
        
        while(q.size()>0){
            
            Pair rem = q.removeFirst();
            int i = rem.i , j = rem.j ; 
            
//if we get to first col all numbers will be ignored from this point and we have already reached our answer 
            if(i == 0 || j == 0)
            System.out.println(rem.psf);
            
/* 2 calls will be made from last coloumn of include and exclude 
recursive call will stop if encounters false anywhere while 
retracing 
*/

            else{
                
                boolean exec = dp[i-1][j];
                if(exec)
                q.add(new Pair(i-1 ,j , rem.psf));    // i-1 is added as array is i-1 of dp
                
                if(j>= arr[i-1]){
                    boolean inc = dp[i-1][j - arr[i-1]];
                    
                    if(inc)
                    q.add(new Pair(i-1,j-arr[i-1],(i-1)+" "+ rem.psf));
                }
            }
        }
    }
}













                        


                        

import java.io.*;
import java.util.*;

public class Main {

   private static class Pair {
      String psf;
      int i;
      int j;

      public Pair(String psf, int i, int j) {
         this.psf = psf;
         this.i = i;
         this.j = j;
      }
   }
   public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      int m = Integer.parseInt(br.readLine());
      int[][] arr = new int[n][m];

      for (int i = 0; i < n; i++) {
         String str = br.readLine();
         for (int j = 0; j < m; j++) {
            arr[i][j] = Integer.parseInt(str.split(" ")[j]);
         }
      }
        int max = Integer.MIN_VALUE;    //answer variable
        
      int dp[][] = new int[m][n];
      
      //filling last col
      for(int i = 0 ; i < m ; i++)
      dp[i][n-1] = arr[i][n-1];
      
      //now Traversing col wise from 2nd last col and finding minimum and also adding our own cost in it
      
        for(int j = n - 2 ; j >= 0 ; j--){
            
            for(int i = 0 ; i < m ;i++){
                
                //if first row
                if(i == 0 ){
                    dp[i][j] = Math.max(dp[i][j+1],dp[i+1][j+1]) + arr[i][j]; 
                    max = Math.max(max , dp[i][j]);
                }
                //if last row
                else if(i == m-1){
                    dp[i][j] = Math.max(dp[i][j+1],dp[i-1][j+1]) + arr[i][j];
                max = Math.max(max , dp[i][j]);
                }
                
                
                //rest of the matrix
                else{
                    dp[i][j] = Math.max(dp[i-1][j+1],Math.max(dp[i][j+1],dp[i+1][j+1])) + arr[i][j];
                
                max = Math.max(max , dp[i][j]);
                }
                
            }
        }
        
        System.out.println(max);
        // for(int i = 0 ; i < m ; i++){
        //     for(int j  = 0 ; j < n ; j++)
        //     System.out.print(dp[i][j] + " ");
            
        //     System.out.println();
        // }
        
        BFS(dp,max);
      
   }
   
   public static void BFS(int[][]dp,int maxcost){
       
       ArrayDeque<Pair> q = new ArrayDeque<>();
       
       //adding max element of first row and calling BFS
       for(int i = 0 ; i < dp.length ; i++)
       if(dp[i][0] == maxcost)
       q.add(new Pair(i+ "",i , 0));
       
       while(q.size()>0){
           
           Pair rem = q.removeFirst();
           int i = rem.i ; 
           int j = rem.j;
           
           //last col
           if(j == dp[0].length -1){
               System.out.println(rem.psf);
           }
           //first row
           else if(i == 0){
               int max = Math.max(dp[i][j+1],dp[i+1][j+1]);
               
               if(max == dp[i][j+1])
               q.add(new Pair(rem.psf + " d2",i , j+1));
               
               if(max == dp[i+1][j+1])
               q.add(new Pair(rem.psf +" d3" , i+1 , j+1));
           }
           
           //last row
           else if(rem.i == dp.length - 1){
               int max = Math.max(dp[i-1][j+1],dp[i][j+1]);
               
               if(max == dp[i-1][j+1])
               q.add(new Pair(rem.psf + " d1",i-1 , j+1));
               
               if(max == dp[i][j+1])
               q.add(new Pair(rem.psf + " d2",i , j+1));
           }
           
           //rest of the matrix
           else{
               int max = Math.max(dp[i-1][j+1],Math.max(dp[i][j+1],dp[i+1][j+1]));
               
               if(max == dp[i-1][j+1])
               q.add(new Pair(rem.psf + " d1",i-1 , j+1));
               
               if(max == dp[i][j+1])
               q.add(new Pair(rem.psf + " d2",i , j+1));
               
               if(max == dp[i+1][j+1])
               q.add(new Pair(rem.psf +" d3" , i+1 , j+1));
           }
       }
   }


}

import java.io.*;
import java.util.*;

public class Main {

   private static class Pair {
      String psf;
      int i;
      int j;

      public Pair(String psf, int i, int j) {
         this.psf = psf;
         this.i = i;
         this.j = j;
      }
   }

   public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      int m = Integer.parseInt(br.readLine());
      int[][] arr = new int[n][m];

      for (int i = 0; i < n; i++) {
         String str = br.readLine();
         for (int j = 0; j < m; j++) {
            arr[i][j] = Integer.parseInt(str.split(" ")[j]);
         }
      }

      int dp[][] = new int[m][n];
      
      //last cell
      dp[m-1][n-1] = arr[m-1][n-1];
      
      //last row
      for(int j = n-2 ; j >= 0 ; j--)
      dp[m-1][j] = dp[m-1][j+1] + arr[m-1][j];
      
      //last col
      for(int i = m-2 ; i >=0 ; i--)
      dp[i][n-1] = dp[i+1][n-1] + arr[i][n-1];
      
      //rest of the matrix
      for(int i = m -2 ; i >= 0 ;i--){
          for(int j = n-2 ; j >= 0 ;j--){
              
              dp[i][j] = Math.min(dp[i][j+1],dp[i+1][j]) ;
              
              //adding your cell's cost
              dp[i][j] += arr[i][j];
          }
      }
      
        //answer stored in dp[0][0]
        System.out.println(dp[0][0]);
        
        //now we will use BFS to find all paths of minimum cost
        
        BFS(dp);
      
   }
   
   public static void BFS(int[][] dp){
       
       ArrayDeque<Pair> q = new ArrayDeque<>();
       q.add(new Pair("" , 0 , 0)); //adding first element
       
       while(q.size()>0){
          Pair rem = q.removeFirst();
          
          //if we have arrived at the last element
          if(rem.i ==dp.length-1 && rem.j == dp[0].length-1)
          System.out.println(rem.psf);
          
          //if last row we can move only right
          else if(rem.i == dp.length - 1)
          q.add(new Pair (rem.psf + "H", rem.i, rem.j+1));
          
          //if last col we can move only down
          else if(rem.j == dp[0].length - 1)
          q.add(new Pair(rem.psf + "V", rem.i+1, rem.j));
          
          //if we are in rest of the matrix
          else{
              
              //if horizontal element is smallest
              if(dp[rem.i][rem.j+1] < dp[rem.i+1][rem.j])
              q.add(new Pair (rem.psf + "H", rem.i, rem.j+1));
              
              //if vertical element is smallest
              else if(dp[rem.i+1][rem.j] < dp[rem.i][rem.j+1])
              q.add(new Pair(rem.psf + "V", rem.i+1, rem.j));
              
              //if both are equal
              else{
                q.add(new Pair(rem.psf + "V", rem.i+1, rem.j));
                q.add(new Pair (rem.psf + "H", rem.i, rem.j+1));
                
              }
          }
          
       }
   }

}

class Solution {
    
    //this is a dp problem , count stairs with minimum jumps
    public int jump(int[] nums) {
        int n = nums.length ;

        //every index stores minimum number of jumps from itself to last index
        //we take Integer to store null for indexes from where there is no path
        Integer dp[] = new Integer[n];   

        //jump from n to n will be 0
        dp[n-1] = 0;
        
        /*
        while iterating from right to left find minimum jumps of from that index
        to the last index
        */
        for(int i = n - 2;i >=0 ;i--){
            
            //if jumps are greater than 0
            if(nums[i] > 0){
                int min = Integer.MAX_VALUE;

                /*
                take jumps from 1 to nums[i] from current index amd see which 
                next index gives you the minimum ans
                 */
                for(int j = 1 ; j <= nums[i] && i+j < n ;j++){

                    //take minimum jumped index answer 
                    if(dp[i+j] != null)
                    min = Math.min(min , dp[i+j]);
                }
                
                //now add 1 for your cell's jump
                // if all jumps lead to null, min will stay as it is
                if(min!= Integer.MAX_VALUE){
                    dp[i] = min+1;
                    System.out.print(dp[i]);
                }
                
            }
                
            
        }

        return (int)dp[0];
    }
}

class Solution {
    public int max = 0;
    public int maximalSquare(char[][] matrix) {
        
    //Q-1 of dp level 2 , every cell denotes maxmimum submatrix square they can make

        //dividing the matrix in 4 parts and solving them indivisually 
        
        int m = matrix.length , n = matrix[0].length;
        int dp[][] = new int[m][n];

    //max subsquare last row can make will be 1 if there is a 1 present in matrix cell
        for(int j = 0 ; j < n ; j++){
            dp[m-1][j] = matrix[m-1][j] -'0' ;
            max = Math.max(max , dp[m-1][j]);
        }
        

    //max subsquare last col can make will be 1 if there is a 1 present in matrix cell
        for(int i = 0 ; i < m; i++){
            dp[i][n-1] = matrix[i][n-1] -'0' ;
            max = Math.max(max , dp[i][n-1]);
        }
        

    //rest of the matrix 

        for(int i = m-2 ; i >= 0 ; i--){
            for(int j = n-2 ; j >= 0 ; j--){

                if(matrix[i][j] == '1'){
                    //minimum of next , below and diagnolly below cell + 1
                 dp[i][j] = Math.min(dp[i][j+1], Math.min(dp[i+1][j+1],dp[i+1][j])) +1;

                 max = Math.max(max , dp[i][j]);
                }
                
            }
        }

        return max*max;     //we have to return area
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        /* LIS in O(nlogn) -> shorturl.at/tyJZ7
        
        we make a dp array of length n where every cell denote the last element
        of ith length LIS , we make an upperbound function which returns the 
        just greater or equal to target index where we keep updating the values
        if we encounter another smaller value than previously stored at index

        we do this so that we can make a longer LIS in the future , in the end 
        we traverse reversely and at any index if we find value other than INTMAX
        we return that index + 1 which denotes length of MAX LIS;
        */

        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp , Integer.MAX_VALUE);

        //traverse the array use upperbound function to update values
        for(int i = 0 ; i < n ; i++){
            int idx = upperBound(dp , 0 , i ,nums[i]);
            dp[idx] = nums[i];           
        }

        //traverse reversely to find the max LIS 
        for(int i = n-1 ; i>=0 ; i--){
            if(dp[i] != Integer.MAX_VALUE)
            return i+1;
        }

        return -1;  //will never reach this statement
    }

    //upperbound returns just greater or equal to value index for updating value
    public int upperBound(int[] dp , int low , int high , int target){

        while(low <= high){
            int mid = low + (high - low)/2;

            if(dp[mid] == target) 
            return mid;
            
            else if(dp[mid] > target)
            high = mid-1;

            else
            low = mid+1;
        }

        return low;
    }
}

class Solution {
    public static int M = (int)(Math.pow(10, 9) + 7);
    public long mod(long val){
        return val % M;
    }
    

    public long add(long val1 , long val2){
        return mod(mod(val1) + mod(val2));
    }
    

    public long mul(long val1 , long val2){
        return mod(mod(val1) * mod(val2));
    }

    public int kConcatenationMaxSum(int[] arr, int k) {
        //ques 43 of dp playlist , kadanes algo 
        System.out.println(arr.length);
        if(k == 1){
            return Math.max((int)mod(kadanes(arr)) , 0);
        }
        

        else{
            //find total sum
            long sum = 0  ;
            int n = arr.length;

            for(int i = 0 ; i < n ; i++)
            sum = sum + arr[i];

            //make an array of double size to store first 2 repetition
            int narr[] = new int[2*n];

            for(int i = 0 ; i < 2*n ; i++)
            narr[i] = arr[i%n];

            //if sum < 0 , find kadanes of first 2 repetition only 
            if(sum < 0){
                int MAS = (int)mod(kadanes(narr));

                return MAS < 0 ? 0 : MAS;
            }
            
            //if sum >= 0 find kadanes of first and last repetition and add
            //(k-2) * sum
            else {

                int MAS = (int)add(kadanes(narr) ,mul(k-2, sum));
                return MAS < 0 ? 0 : MAS;
            }
        }

    
    }
    public long kadanes(int[] arr){
        int n = arr.length ;
        long csum = arr[0] , omax = arr[0];
        
        for(int i = 1 ; i < n ; i++){
            long val = arr[i];
            if(csum > 0)
            csum = csum + val;

            else
            csum = val;

            omax = Math.max(omax , csum);
        }

        return omax;
    }
}

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        /* Q13 of dp playlist , the question is reducable to LIS , we sort the
        array based on width now we have sorted width so we find LIS on heights
        
        its very important to sort the heights in descending order if widths are
        equal as its given that , widths and heights both should be strictly 
        greater
        */
        int n = envelopes.length;
        
        /* sorting the enevelopes array based on width , we use thiss and otherr
        as we cannot use legacy naming this and other , we sort the array based
        on width and if widths are equal we sort them based on descending heights
        */
        Arrays.sort(envelopes , new Comparator<int []>(){
            
            public int compare(int thiss[] , int otherr[]){
                if(thiss[0] == otherr[0])
                return otherr[1] - thiss[1];

                else
                return thiss[0] - otherr[0];
            }
        });

        /* we initialise the dp array with MAX_VALUE , then traverse the array
        and keep placing elements based on patience sort or deck of cards , every
        cell in dp denotes last element of ith LIS , we find position of new 
        values using upperbound and keep updating the ith index which stores
        last element for ith index.
        */
        int[] dp = new int[n];
        Arrays.fill(dp , Integer.MAX_VALUE);

        for(int i = 0 ;i < dp.length ; i++){
            
            int idx = upperBound(dp , 0 , i ,envelopes[i][1]);
            dp[idx] = envelopes[i][1];
        }

        //traverse reversely and find the first not intmax value which is our LIS
        for(int i = n-1 ; i>=0 ; i--){
            if(dp[i] != Integer.MAX_VALUE){
                return i+1;
            }
        }

        return -1;  //would never reach this statement
    }

    //function to find just greater or equal to index
    public int upperBound(int[] dp , int low , int high , int target){

        while(low <= high){
            int mid = low + (high - low)/2;

            if(dp[mid] == target)
            return mid;

            else if(dp[mid] > target)
            high = mid-1;

            else
            low = mid+1;
        }
        return low;
    }
}

class Solution {
    public int maxCoins(int[] nums) {
        //this is a question of matrix chain multiplication dp playlist vid23

        //adding an extra 1 in the end of the array 
        int n = nums.length;
        int dp[][] = new int[n][n];

        for(int gap = 0; gap < n ; gap++){

            for(int i = 0 , j = gap ; j < n ; i++ , j++){ 
                
                int max = Integer.MIN_VALUE;
                for(int k = i ; k <= j ;k++){

                    int left = k==i ? 0: dp[i][k-1] ;
                    int right = k==j ? 0: dp[k+1][j] ;
                    
                    //cost = nums[i-1] * nums[k] * nums[j+1]
                    //handling for i==0 and j == n-1
                    int cost = nums[k];
                    
                    cost *= i > 0 ? nums[i-1] : 1;
                    cost *= j != n-1 ? nums[j+1] :1;

                    max = Math.max(max , left + right + cost);
                }
                
                dp[i][j] = max;
                
            }
        }

        return dp[0][n-1];

    }
}