Problem Description

Malaika is very fond of strings so whenever she gets some free time, she will keep herself engaged in string based activities.

One day, she came across a question where she will be given two strings X & Y and asked to form X from Y. The rules for forming the string are given below.

• The string X should be formed with the concatenation of the sub strings of Y. You can also select the sub strings from Y in reversed order.
• The length of the sub strings selected from Y should be greater than or equal to one.
• Aim is to minimize the number of sub strings that are selected from Y and concatenated to form X.
• A term String Factor is defined which is calculated as (number of sub strings selected from Y) * S + (number of sub strings selected from reversed Y) * R, where S and R given in the input.
• You also have to minimize the String Factor while maintaining the minimum number of sub strings.

Given two strings X and Y and two integers S and R, find the minimum String Factor of the string X following above rules.

Constraints

1 <= lengths of X,Y < $$$10^4$$$

0 <= S, R < $$$10^3$$$

X, Y consists of lower case alphabets only.

Input

First line consists of string X. Second line consists of string Y. Third line consists of two integers S and R separated by space.

Output

Form the string X from string Y following the above rules and print the String Factor of X. Print 'Impossible' if X can't be formed from Y.

Time Limit (secs)

1

Examples

Example 1

Input

niveditha
lavekdahnita
3 5

Output

17

Explanation For forming the string niveditha from lavekdahnita, select sub strings 'ni' from Y, 've' from Y, 'd' from Y, 'it' from Y, 'ha' from reversed Y. No other selections can give less than five sub strings. String Factor = (number of sub strings selected from Y) * S + (number of sub strings selected from reversed Y) * R = (4*3) + (1*5) = 17

Example 2

Input

abcdef
pafedexycbc
4 2

Output

6

Explanation For forming the string abcdef from pafedexycbc, select the sub string 'a' from reversed Y, 'bc' from reversed Y, 'def' from reversed Y. No other selections can give less than three sub strings. String Factor = (number of sub strings selected from Y) * S + (number of sub strings selected from reversed Y) * R = (0*4) + (3*2) = 6

How to approach this problem?

Bittu is a chocolate-loving kid playing a game where he can choose bags of chocolates. Each bag has a different number of chocolates. Bittu starts with k chocolates and 1 point. He has two choices for each bag:

1. Accept the Bag:

• If the chocolates in the bag are fewer than or equal to the chocolates Bittu has, he won't accept the bag. Instead, he'll deduct the bag's chocolates from his stash and gain one point.

• If the chocolates in the bag are more than what Bittu has, he can accept the bag. His chocolate stash increases by the bag's chocolates, and he loses one point.

1. Ignore the Bag:

• Bittu can choose to ignore any number of bags without any consequences.

The goal is to maximize Bittu's points. Given an array "chocolates" with the number of chocolates in each bag, and the initial number of chocolates Bittu has, determine the maximum points he can achieve by selecting bags wisely

In simpler terms, he wants to acquire the maximum number of points while following the above mentioned rules.

Constraints

n — length of the array

1 <= n <= 1000

0 <= chocolates[i] <= 10^5

Input

First line consisting of the number of chocolates in n bags separated by space.

Second line consists of an integer depicting the number of chocolates that Bittu has, initially.

Output

Print the maximum points that Bittu can acquire.

Someone please help me with this problem. I am trying a DP solution but it is giving MLE.

Jack has invited her friend Tina to play a game of numbers.The game is as follows:

There are a total of 'N' numbers (1,2,3....N) with Jack. He has to share 'X' of them with Tina. After sharing 'X' numbers, Jack has a set of '(N-X)' numbers and Tina has a set of 'X' numbers. Consider Jack's set as J and that of Tina 'T'. Now, the distribution should happen in such a way that each number from set 'J' should have a GCD of '1' from set of numbers in 'T'. Formally, GCD(x,y) = 1, where 'x' are the elements of set 'J', and 'y' are the elements of set 'T'.

Input: Value of N and X

Output: If the above condition is possible, print "Yes". Followed by (separated by SPACE), the number of components of 'T' (X number of components from set). If condition is not satisfied then print "No".

Example 1:

Input:

N = 4, X = 1

Output: Yes 3

Let us try to understand it with and example. Consider a set of N = 4 and X = 1. It means that the entire set Contains S= [1,2,3,4], and 'J' contains number from this set. He also needs to make sure that each number from his, set and Tina's set have a GCD of '1'.

By looking into the elements of the Jack's set, we can clearly see that element '2' and '4' should be in same set otherwise they will make a GCD of 2, which will ultimately not satisfy the above condition.

If we take the element '3' from the Jack's set, and give to Tina, then we can have all the conditions satisfy because the remaining element of Jack's set (1, 2, 4) will have a common GCD of 1 with the element of Tina's set which is 3.

Hence the output is : Yes 3

Example 2:

Input:

N = 6, X = 3

Output:

No

Explanation:

In this scenario, we have to give 3 elements to Tina. Initially Jack's set contains [1, 2, 3, 4, 5, 6]. The best case which we can think of is to share the prime numbers to Tina and leave the rest with Jack, or vice- versa.

In that case, Jacks's set = [2, 4, 6] Tina's set = [1, 3, 5]

But, if you see closely the element '6' and '3' will have a GCD of 3, hence the conditions will fall.

And the result will come out to be No.

Hence the output is: No

Example 3:

Input:

N = 4, X = 3

Output: Yes 1 2 4

Someone kindly solve this with explanation. Thanks.

Given a board with an integer 'n' written on it, select an integer 'x' from the board. For each, 'i' from 1 to 'x', if the remainder when 'x' is divided by 'i' is 1, add the integer (x-i) to the board. Find out the maximum number of distinct integers that can be present on the board.

Example- n = 4

Initially, only the given number 4 is on the board. There is one value that leaves a remainder of 1: 4%3=1. Add the value 4-3=1 to the board, so it now contains [1,4]. There is no longer 'i' such that 1%i=1. There are 2 distinct integers on the board, so return 2.

Constraints- 1<=n<=1000

If someone could explain the approach then it would be very helpful. Thanks.

Link to the problem: https://cses.fi/problemset/task/1192/

I am getting time limit exceeded for Test cases #10 and #17 for this question. I am stuck with this for a long time and unable to figure it out as to why this is occuring. Need some help. My code is given below. Thanks in advance.

import java.util.*;
public class Crooms
{
    static int direction[][]={{1,0},{0,1},{-1,0},{0,-1}};
    static char ch[][]=new char[1001][1001];
	static int vis[][]=new int[1001][1001];
	static int n=0,m=0;
	public static void main(String[] args) {
	    Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
	    int count=0;
	    for(int i=0;i<n;i++)
	    {
	        ch[i]=sc.next().toCharArray();
	    }
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            if(ch[i][j]=='.' && vis[i][j]!=-1)
	            {
	                vis[i][j]=-1;
	                dfs(i,j);
	                count++;
	            }
	        }
	    }
	    
		System.out.println(count);
	}
	public static boolean boundary_check(int x, int y)
	{
	    return x>=0 && y>=0 && x<n && y<m && ch[x][y]=='.' && vis[x][y]!=-1;
	}
		public static void dfs(int x, int y)
	{
	        for(int i=0;i<4;i++)
	        {
	            int nx=x+direction[i][0];
	            int ny=y+direction[i][1];
	            if(boundary_check(nx,ny))
	            {
	            vis[nx][ny]=-1;
    	        dfs(nx,ny);
	            }
	        }
	}
}