시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 123 69 43 51.807%

문제

생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤케이크를 준비했다. 롤 케이크에는 장식이 존재하여 일정한 크기로 자를 수 없다. 그래서 주성이는 미리 롤 케이크를 친구들의 수대로 잘라서 가장 작은 조각의 크기를 미리 알아보고 싶다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 주성이가 롤 케이크를 몇 번 잘라야 하는지 리스트로 알려주기로 했다. 이 리스트에 있는 횟수대로 롤 케이크를 자를 때 가장 작은 롤 케이크의 길이가 가장 크게 되는 길이를 구해보자. 

예를 들어 70cm의 롤 케이크에 자를 수 있는 지점이 5군데(10cm, 20cm, 35cm, 55cm, 60cm)가 있다고 하자. 만약 리스트의 숫자 중 하나가 3이라면 20cm, 35cm, 55cm 지점을 자를 때, 가장 작은 조각의 길이는 15cm로 최대가 된다.

입력

첫 번째 줄에 자르는 횟수가 담긴 리스트의 길이 와 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000 , 1 < L ≤ 4,000,000)

다음 M 줄에 걸쳐 자를 수 있는 지점을 나타내는 정수 Si 가 주어진다. (1 ≤ S < L)

다음 N 줄에 걸쳐 자르는 횟수를 나타내는 정수 Qi 가 주어진다. (1 ≤ Q ≤ M)

Si와 Qi 는 중복된 지점은 주어지지 않으며 오름차순으로 주어진다.

출력

개 줄에 걸쳐 각 리스트에 있는 횟수대로 롤 케이크를 잘랐을 때 가장 작은 조각의 길이가 최대가 되는 길이를 출력한다.

예제 입력 1

2 5 70
10
20
35
55
60
3
4

예제 출력 1

15
10