30977번 - 금강산도 식후경

문제

진주 나들이를 온 보선이는 남강유등축제에 갔다. 남강유등축제에는 화려하고 다채로운 조형물과 재미있는 공연이 많지만, '금강산도 식후경'이 좌우명인 보선이는 많은 먹거리가 있는 푸드트럭 존을 찾았다. 그런데 이상하게도 푸드트럭 존이 보이지 않았다. 알고 보니, 남강유등축제에는 푸드트럭 존이 아닌 쿠킹 존이 있었다.

이 쿠킹 존에서는 재료 $N$ 종류를 판다. 재료마다 자극도가 $T_1,ドル $\dots,ドル $T_N$으로 정해져 있고, 모든 재료는 요리에 아무리 많이 쓰여도 남을 만큼 충분히 많다. 이 재료들 중에서 재료의 종류와 각 재료의 개수를 마음대로 정해서 음식을 요리해 먹어야 한다. 완성된 음식의 자극도는 사용된 재료들의 자극도의 합이 된다. 이러한 방식으로 한 번 요리를 할 때마다 일정한 돈을 내야 한다. 그래서 쿠킹 존에서의 요리의 횟수는 딱히 제한이 없다. 그러나 하나의 음식에 들어가는 재료의 개수는 정해져 있다. 재료를 너무 많이 넣으면 시간도 오래 걸리고 맛도 없어지고, 재료를 너무 적게 넣으면 맛이 단조롭기 때문에 하나의 음식에 넣는 재료의 개수는 정확하게 $M$개로 제한된다.

보선이는 $K$개의 음식을 먹을 계획이다. 그와 동시에 보선이는 미식가이기 때문에 먹게 되는 $K$개의 음식의 자극도를 중요시한다. 이에 대한 자세한 설명은 다음과 같다. $i$번째로 먹는 음식의 자극도를 $F_i$라 하고 \(D_i = \left(F_i - F_1\right)\)이라 한다면, 보선이의 식사 계획은 증가하는 수열 $D = \{D_1, \dots, D_K\}$로 나타낼 수 있다. 또한, $D_1$은 항상 0이다. 그리고 비슷한 자극도의 음식끼리는 헷갈릴 수 있기 때문에, $F_1$과의 자극도 차이가 $D_1$ 이상 $D_K$ 이하이면서 식사 계획 $D$에 포함되지 않는 음식은 만들어질 수 없어야 한다.

식사 계획 $D$에 대한 설명을 돕기 위해 간단한 예를 하나 들어보겠다. 보선이의 식사 계획 $D$가 수열 $\{0, 2, 3\}$이라고 생각해보자. 만약 $F_1$을 3으로 골랐다면, $F_2$는 5가 되어야 하며, $F_3$은 6이 되어야 한다. 그리고 $F_1$과의 자극도 차이가 $D_1$ 이상 $D_K$ 이하이며 식사 계획 $D$에 포함되지 않는 4를 자극도로 갖는 음식은 만들어질 수 없어야 한다. 만약 자극도가 4인 음식이 만들어질 수 있다면, $F_1$을 3으로 고를 수 없게 된다.

보선이가 재료 $M$개를 사용하여 만들 수 있는 모든 음식을 만들었을 때, 위 조건을 만족시킬 수 있는 $F_1$로 적합한 자극도의 개수를 구해보자.

입력

첫 번째 줄에는 재료 종류의 개수 $N,ドル 하나의 음식에 넣어야 하는 재료의 개수 $M,ドル 먹으려는 음식의 개수 $K$가 공백으로 구분되어 주어진다. $(1 ≤ N, M ≤ 1,000円; 1 ≤ K ≤ 1,000円,000円)$

두 번째 줄에는 $T_1,ドル $\dots,ドル $T_N$이 공백으로 구분되어 주어진다. $T_i$는 $i$번째 재료의 자극도를 나타낸다. $(1 ≤ T_i ≤ 1,000円)$

세 번째 줄에는 $D_1,ドル $\dots,ドル $D_K$가 공백으로 구분되어 주어진다. 이는 보선이의 식사 계획을 나타내는 증가하는 수열 $D$를 나타낸다. $(0 ≤ D_i ≤ 1,000円,000円; D_1 = 0)$

입력에서 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 조건을 만족시킬 수 있는 $F_1$로 적합한 자극도의 개수를 출력한다.

제한

노트

Python 3 사용자는 PyPy3로 제출할 것을 권장한다.