눈송이 탕후루 만들기
면접 대비시간 제한2초메모리 제한512 MB
원점 (0, 0)에서 후보 끝점까지 꽂는 꼬치 하나가 꿸 수 있는 과일의 최대 개수를 구합니다.
문제
숙명여자대학교에 입학한 새내기들은 귀여운 눈송이를 좋아해서 눈송이 탕후루를 만들려고 한다. 눈송이 모양의 과일들이 2차원 좌표 평면 위에 놓여 있다. 꼬치는 에서 끝점 까지 놓이며, 끝점을 포함한 선분 위의 모든 과일을 꽂는다. 꼬치의 끝점을 놓을 수 있는 위치 후보는 개이다. 후보 중 하나를 골라 꼬치 하나로 꽂을 수 있는 과일의 수를 최대로 할 때, 그 수를 구한다.
입력
첫 줄에 과일의 수 과 꼬치의 끝점을 놓을 수 있는 위치의 수 이 정수로 주어진다. (; ) 다음 개의 줄에 과일의 위치 가 공백으로 구분되어 주어진다. (, , 는 정수) 중복된 과일의 위치는 주어지지 않는다. 다음 개의 줄에 꼬치의 끝점을 놓을 수 있는 위치 가 공백으로 구분되어 주어진다. (, , 는 정수) 중복된 꼬치의 끝점은 주어지지 않는다. 또는 가 인 경우는 존재하지 않는다. 와 가 같은 경우는 존재할 수 있다.
출력
과일을 최대한 많이 꽂을 수 있을 때, 꽂히는 과일의 수를 출력한다.