맛집 가이드

윤이는 UNIST 주변의 음식점에 대한 정보를 제공하는 가이드 앱, 일명 “UNIST 가이드”를 만들기로 했다. 윤이는 근처 음식점 중에서 $N$개의 음식점을 추천하기로 정하고, 음식점에 $1$번부터 $N$번까지 번호를 붙였다.

윤이는 이 음식점들에 대한 정보를 조사하다가, 두 명의 음식 평론가 동규와 원이가 각각 $N$개의 음식점에 순위를 매긴 자료를 찾았다. 윤이는 두 순위표를 바탕으로 음식점 등급을 매기려고 한다. 음식점 등급은 어떤 양의 정수 $S$에 대해, $1$ 이상 $S$ 이하의 정수 별점으로 나타낸다. 별점이 높을수록 맛있는 음식점이라는 뜻이다.

음식점 등급은 두 평론가가 매긴 음식점 순위에 위배되지 않아야 한다. 다시 말해, 어떤 음식점 X의 등급이 음식점 Y의 등급보다 높다면, 이는 두 평론가의 순위표에서 모두 음식점 X의 순위가 음식점 Y보다 높다는 것을 의미한다. 역은 성립하지 않아도 된다.

또한, 각각의 등급에 대해서 해당 등급을 받은 음식점이 적어도 $K$개 있어야 한다.

윤이는 음식점 정보가 구체적일수록 UNIST 가이드의 신뢰도가 올라갈 것이라고 분석해서, 음식점 등급을 최대한 세분화하려고 한다. 즉, 윤이의 목표는 최고 별점 $S$가 최대한 크도록 음식점 등급을 매기는 것이다. 윤이가 조건을 만족하도록 음식점 등급을 매겼을 때 등급의 개수는 최대 얼마인가?

첫 번째 줄에 음식점의 개수 $N$과 등급별 최소 음식점 개수를 나타내는 정수 $K$가 공백으로 구분되어 주어진다. ($1\le K\le N\le 200\ 000$)

두 번째 줄에 평론가 동규가 평가한 순위가 높은 순서대로 $N$개의 음식점 번호가 공백으로 구분되어 주어진다.

세 번째 줄에 평론가 원이가 평가한 순위가 높은 순서대로 $N$개의 음식점 번호가 공백으로 구분되어 주어진다.

주어지는 음식점 번호는 $1$ 이상 $N$ 이하의 정수이며, 각 줄 내에서 중복되지 않는다.

윤이가 음식점 등급을 최대한 세분화하도록 등급을 매겼을 때, 등급의 개수를 출력한다.