Mudstock Bis

Holypolygons 협회는 회원들이 Mudstock 벌판에서 처음 모였던 집회의 10주년을 기념하기 위해 Mudstock Bis라는 대규모 축제를 연다.

회원들은 Holypolyland 곳곳의 작은 마을에 흩어져 산다. 마을들은 $\ell$개의 철도 노선($1 \le \ell \le 350$)을 따라 놓여 있고, 노선은 $1$번부터 $\ell$번까지 번호가 매겨진다. 어떤 노선도 길이가 $500$ km를 넘지 않는다. 모든 노선은 수도에서 시작해 지방을 향해 방사형으로 뻗어 나가며, 노선끼리는 서로 교차하지 않는다. 수도를 제외한 각 마을은 정확히 하나의 노선 위에 있다. 각 노선에는 마을이 $1$개 이상 $100$개 이하 있고, 한 마을에 사는 회원 수는 $100$명 이하이다.

수도가 아닌 각 마을은 좌표 $(k, n)$으로 유일하게 나타낸다. 여기서 $k$는 마을이 놓인 노선의 번호이고, $n$은 그 노선에서의 마을 순번이다. 한 노선의 마을은 수도에서 가까운 쪽부터 차례로 번호가 매겨진다. 모든 노선의 시작점인 수도의 좌표는 $(0, 0)$이다.

협회는 축제가 끝난 뒤 집으로 돌아가는 모든 회원에게 기차표를 지원하며, 표값은 이동한 거리 $1$ km당 $1$이다. 모든 회원의 귀가 비용 합이 가장 작아지도록 축제를 열 마을을 정해야 한다.

철도망 정보를 읽어, 모든 회원의 총 이동 비용이 최소가 되는 마을을 찾고, 그때의 최소 총 비용과 선택한 마을을 출력하는 프로그램을 작성하라.

첫째 줄에 두 정수, 철도 노선의 수 $\ell$ ($1 \le \ell \le 350$)과 수도에 사는 회원 수 $m$ ($0 \le m < 100$)이 주어진다.

다음 $\ell$개의 줄에는 $1$번 노선부터 $\ell$번 노선까지 각 노선의 정보가 공백으로 구분된 정수들로 주어진다. 각 줄은 그 노선 위의 마을 수(수도를 제외한 양의 정수)로 시작한다. 이어서 수도에서 먼 쪽으로 가며 각 마을마다 두 정수가 주어지는데, 그 마을에서 수도 방향으로 가장 가까운 마을(또는 수도)까지의 거리(양의 정수)와 그 마을에 사는 회원 수(음이 아닌 정수)이다.

첫째 줄에 모든 회원의 귀가 기차 이동 비용의 최솟값을 출력한다.

둘째 줄에 축제를 열 마을의 좌표 $k$와 $n$을 공백 하나로 구분하여 출력한다. 수도는 0 0으로 나타낸다.

여러 마을에서 최소 총 비용이 같다면, 노선 번호 $k$가 가장 작은 마을을 출력하고, 그래도 같다면 순번 $n$이 가장 작은 마을을 출력한다. 이 규칙에서 수도 $(0, 0)$은 다른 모든 마을보다 작은 것으로 보므로, 답은 유일하게 정해진다.