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