개구리 매칭
시간 제한1초메모리 제한1024 MB
각 개구리에 대해 거리 K 이하의 첫 점프가 강제되고 이후 1칸당 L의 체력이 드는 규칙에서 두 개구리의 체력 소모 합의 최솟값을 구하고, 그 값이 가장 작은 개구리의 번호를 찾는다.
문제
개구리 주호는 축 위에 사는 마리의 개구리 중 하나를 선택하여 만나려고 한다. 번째 개구리를 선택해 만나려 했을 때, 개구리 주호는 에서, 번째 개구리는 에서 동시에 출발하여 움직인다.
이때, 두 개구리는 각각 다음과 같이 움직인다. 실제로 좌표가 변하지 않더라도 아래 과정을 따라야 함에 유의하라.
- 상대 개구리를 바라보는 방향으로 움직이며, 반대 방향으로는 움직이지 않는다.
- 상대 개구리를 뛰어넘지 않는다.
- 상대 개구리를 향해 움직일 때 맨 처음에 반드시 점프를 한 번 해야 한다.
- 점프를 한 번 한 뒤에는 걸어서 움직여야 한다.
- 점프하거나 걸을 때는 반드시 정수 거리만큼 움직여야 한다.
이 개구리들은 신기한 특징이 있는데, 최대 거리 만큼 점프할 수 있으며, 정확히 거리 만큼 점프하기 적합하게 진화했다는 점이다. 그래서 거리 만큼 점프하면 체력이 만큼 소모된다. 즉, 이면 제자리로 점프하면서 만큼의 체력이 들고, 이면 만큼 점프하고 만큼의 체력이 소모된다.
한 번 점프한 뒤에는 상대방 개구리를 만날 때까지 걷는다. 이때 씩 걸을 때마다 체력 이 소모된다.
개구리들에게 체력은 생존을 위해 매우 중요하다. 그들은 서로를 향해 움직일 때 서로의 체력 소모의 합이 최소가 되도록 움직인다. 개구리 주호는 마리의 개구리 중 자신과 만나기 위해 소모되는 체력의 합이 가장 작은 개구리 하나를 선택하여 만나려고 한다. 주호를 위해 서로의 체력 소모량의 합의 최솟값과 주호가 만날 개구리의 번호를 찾아주자.
입력
첫째 줄에 와 이 공백으로 구분되어 주어진다.
둘째 줄에 개구리의 위치를 뜻하는 이 공백으로 구분되어 주어진다. 주호를 포함한 모든 개구리의 좌표는 서로 다르다.
셋째 줄에 와 이 공백으로 구분되어 주어진다.
출력
서로의 체력 소모의 합의 최소와 그 개구리의 번호를 공백으로 구분하여 출력하라.
만약 체력 소모의 합이 최소가 되도록 만날 수 있는 개구리가 여러 마리일 경우 그중 아무거나 하나를 출력한다.