23892번 - 바코드 찢기 서브태스크

경기북과학고등학교의 자판기 시스템은 특이해서, 돈 대신 "바코드"라고 불리는 괄호 문자열을 구매에 사용한다.

자판기에는 음료수 $N$개가 들어 있고, 음료수 1개의 가격은 $K$원이다.

여러 종류의 바코드 중에서도, 다음 성질을 모두 만족하는 바코드 (이하 "올바른 바코드") 들만이 1원의 가치를 가진다:

1. 올바른 바코드란 (와 )로 이루어진 문자열이어야 한다.
2. ()는 올바른 바코드이다.
3. 문자열 $X$가 올바른 바코드일 때, 문자열 $(X)$는 올바른 바코드이다.
4. 문자열 $X, Y$가 올바른 바코드일 때, 둘을 이어붙인 문자열 $XY$ 또한 올바른 바코드이다.

올바른 바코드는 주어진 성질을 만족하기만 한다면 가치는 모두 똑같은 1원으로 취급되며, 주어진 성질을 모두 만족하지 못하는 바코드는 구매에 사용될 수 없다. 하지만, 주어진 성질을 만족하지 않는 바코드라도 임의로 찢어 나누었을 때 올바른 바코드가 된다면 구매에 사용하는 것이 가능하다.

예를 들어, 바코드 ())()() 는 0원의 가치를 가진다. 하지만 이를 찢어 (), ), ()() 의 세 바코드로 나누면 셋 중 올바른 바코드가 2개이므로 총 2원만큼의 가치를 가지게 된다. 

이때, 찢고 남은 바코드들을 붙여 새로운 바코드를 만드는 것은 불가능하다.

당신은 지금 긴 길이의 바코드 하나를 가지고 있으며, 이를 적절히 찢어 최대한 많은 개수의 음료수를 구매하려 한다. 바코드는 구매한 각각의 음료수에도 붙어 있으며, 음료수에 붙어있는 바코드의 형태는 모두 같다. 음료수를 구매한 후에는 음료수에 붙어 있던 바코드를 이용해 새로운 음료수를 구매할 수 있다.

$N$, $K$, 그리고 당신이 가지고 있는 바코드와 음료수에 붙어있는 바코드의 형태가 각각 주어질 때, 당신이 살 수 있는 음료수 수의 최댓값을 출력하라.

첫째 줄에 현재 자판기에 있는 음료수의 개수 $N$과 음료수 하나의 가격 $K$가 주어진다. 

둘째 줄에는 당신이 가지고 있는 바코드의 형태가 주어진다.

바코드의 길이가 매우 길 수 있기에, 대신 바코드의 패턴 $S$와 반복 횟수 $P$가 주어진다. 당신이 가지고 있는 바코드는 $S$를 $P$번 반복한 형태이다.

셋째 줄에는 음료수에 붙어있는 바코드의 형태가 둘째 줄과 같은 조건으로 주어진다.

$N$, $K$, $P$는 모두 양의 정수임이, $S$는 (와 )만으로 이루어져 있음이 보장된다. 단, 주어지는 바코드들은 올바른 바코드가 아닐 수 있다.

살 수 있는 음료수 수의 최댓값을 출력한다.

• $1 ≤ N$, $K ≤ 10^{14}$
• $1 ≤ |S| ≤ 10^5$, $1 ≤ P ≤ 10^9$ ($|S|$는 $S$의 길이를 의미한다.)
• 주어지는 수들의 범위가 넓어 32비트 정수형으로 처리할 수 없을 수 있음에 유의하여라.