L. Gula Mineira
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Today is an important day for Matheus "Mathias" Prates: he is taking his final exam in AL2 (Cool Algorithms 2). He arrived early at the Federal University of Minas Gerais (UFMG) to study in the science library, but got so caught up in the review exercises that he is now late for lunch at his favorite campus restaurant, Gula Mineira.

Gula Mineira serves a self-service buffet with $$$n$$$ dishes arranged on a circular table. The table is represented by a circular list: position $$$i$$$ holds the dish identified by the positive integer $$$p_i$$$. Each dish appears at exactly one position.

Matheus has written down a sequence $$$s$$$ of the dishes he would like to take, in the order he wants to add them to his plate. Unfortunately, the restaurant is crowded, and everyone must move around the table in the same direction. If he is at position $$$i$$$ at time $$$t$$$, he may move to the next position ($$$i+1$$$, or $$$1$$$ if $$$i=n$$$), arriving at time $$$t+1$$$, or leave the queue. Leaving and rejoining the queue takes $$$k$$$ seconds and allows him to rejoin at any position. Taking a serving of a dish, even repeatedly, takes no time.

Initially, Matheus is outside the queue and may join at any position for free. Every subsequent departure and reentry costs $$$k$$$ seconds.

He wants to take as many dishes from his wish list as possible, in the listed order, within $$$w$$$ seconds. More formally, he wants to take a longest possible subsequence of $$$s$$$ within this time limit. Dishes skipped in the subsequence need not be visited. Help him finish lunch in time for his exam!

Input

The first line contains four integers $$$n$$$, $$$m$$$, $$$w$$$, and $$$k$$$ ($$$1 \le n \le 2 \times 10^{5}$$$, $$$1 \le m \le 5000$$$, $$$0 \le w,k \le 5000$$$): the number of dishes on the table, the length of the desired sequence, the available time in seconds, and the time needed to leave and rejoin the queue.

The second line contains $$$n$$$ distinct integers $$$p_1,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ identifies the dish at position $$$i$$$.

The third line contains $$$m$$$ integers $$$s_1,\ldots,s_m$$$ ($$$1 \le s_i \le n$$$), the desired sequence of dishes.

Output

Print a single integer: the maximum length of a subsequence of $$$s$$$ that Matheus can take within $$$w$$$ seconds.

Examples
Input
4 3 10 1
2 1 4 3
1 2 3
Output
3
Input
5 5 5 2
1 2 3 4 5
1 3 2 5 4
Output
4
Input
3 4 0 1000
1 2 3
2 1 2 3
Output
2
Note

Explanation for example 2

Here, $$$n=5$$$, and dish numbers coincide with table positions (dish $$$i$$$ is at position $$$i$$$), with $$$k=2$$$ and $$$w=5$$$. The diagram below shows the table, with arrows indicating the permitted direction of movement.

The desired sequence is $$$s=(1,3,2,5,4)$$$. Matheus can take $$$4$$$ dishes within $$$w=5$$$ seconds. It can be shown that no longer subsequence is possible.

Explanation for example 3

Since $$$w=0$$$ and $$$k=1000$$$, Matheus cannot move along the queue or leave it. However, he may join directly at dish $$$2$$$ and take it twice, using no time. This gives the subsequence $$$(2,2)$$$, formed by the first and third elements of $$$s$$$: skipped elements need not be visited. Since no other dish appears more than twice, the answer is $$$2$$$.