금강산도 식후경

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

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

보선이는 $K$개의 음식을 먹을 계획이다. 보선이는 미식가라서 먹게 되는 $K$개의 음식의 자극도를 중요하게 여긴다. $i$번째로 먹는 음식의 자극도를 $F_i$라 하고, $D_i = F_i - F_1$이라 하자. 식사 계획은 증가하는 수열 $D = \{D_1, \dots, D_K\}$로 나타내며, $D_1$은 항상 $0$이다. 비슷한 자극도의 음식끼리는 헷갈릴 수 있으므로, $F_1$과의 자극도 차이가 $D_1$ 이상 $D_K$ 이하이면서 식사 계획 $D$에 없는 음식은 만들어질 수 없어야 한다.

예를 들어 식사 계획 $D$가 $\{0, 2, 3\}$이라고 하자. $F_1$을 $3$으로 고르면 $F_2$는 $5$, $F_3$은 $6$이 되어야 한다. 자극도가 $4$인 음식은 계획에 없고 $F_1$과의 차이가 $D_1$ 이상 $D_K$ 이하이므로 만들어질 수 없어야 한다. 자극도 $4$인 음식을 만들 수 있다면 $F_1$을 $3$으로 고를 수 없다.

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

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

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

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

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

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

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