격자에 마리오, 피치공주, 그리고 쿠파 군단의 몬스터들이 있다. 마리오는 에, 피치공주는 에 있다.
마리오와 모든 몬스터는 매초 동시에 상하좌우로 인접한 칸 하나로 이동한다. 몬스터는 격자 안이면서 피치공주의 칸이 아닌 인접 칸 중 하나를 균등한 확률로 선택한다. 각 몬스터의 선택은 매초 서로 독립이다.
마리오는 피치공주에게 최단 경로로 이동해야 한다. 이동을 마친 직후 마리오와 몬스터가 같은 칸에 있다면 만난 것으로 간주한다. 같은 몬스터를 여러 번 만나면 만날 때마다 만난 몬스터 수에 포함한다.
여러 최단 경로 중 만나는 몬스터 수의 기댓값이 최소인 경로를 택할 때, 그 최소 기댓값을 구해 보자.
첫째 줄에 , , 몬스터가 존재하는 초기 좌표의 수 가 주어진다.
둘째 줄부터 개의 줄에 걸쳐 좌표 , 와 그 칸에 있는 몬스터 수 가 주어진다.
만나는 몬스터 수의 최소 기댓값을 출력한다. 절대 오차 또는 상대 오차가 이하이면 정답으로 인정된다.
, , 이다. 좌표는 서로 다르고 과 은 주어지지 않는다.
입력으로 주어지는 모든 수는 정수이다.