시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 2 2 50.000%

문제

최근들어 젖과꿀의나라에 좋지 않은 소문들이 퍼지고 있다. 몇몇 사람들이 우유 강들에 있는 우유가 상했다고 얘기하기 시작한것이다. 나라에서 조사해본 결과, 그 몇몇 사람들은 젖과꿀나라의 관광 사업을 질투해 옆나라에서 보낸 사람들로 밝혀졌다. 그러나, 이 사실이 안좋은 소문 확산을 멈추지는 못했다. 젖과꿀나라의 정부는 관광 사업을 유지하기 위해, 매일 우유 강들의 신선도를 확인하고자한다.

이를 위해 새로운 우유안전부서가 설립되었고, 우유의 상함 방지를 위한 모든 장비를 갖추고있다. 상함 방지를 위해 사전에 헬리콥터로 우유의 신선도를 체크하기로했다. 신선도 체크를 위해서는 헬리콥터로 강을 건너기만하면 된다.

이러한 검사를 위해 정부가 자금을 지원해야하는데, 문제가 되는것은 신선도를 확인하는 헬리콥터의 경로이다. 헬리콥터는 모든 강을 가장 효율적인 경로로 확인해야한다.

우유 강들은 총 두 방향으로 흐르며 모두 직선으로 흐른다. 북에서 남으로 흐르는 n개의 강들과, 동에서 서로 흐르는 e개의 강들이 있으며 같은 방향으로 흐르는 강들은 모두 평행하다.

정부는 헬리콥터 비행에 필요한 최저 자금을 구하려고하며, 1km당 꿀통 1개가 들어간다. 각 강들 사이의 거리는 주어지고, 이륙 및 착륙에 필요한 비용은 고려하지 않는다. 비행의 시작점과 종착점은 임의로 정할 수 있다.

입력

첫째 줄에는 정수 n과 e가 주어진다(1 ≤ n, e ≤ 1 000).

두번째 줄에는 북에서 남으로 흐르는 강들 사이의 거리들이 주어진다.(동쪽부터)

세번째 줄에는 동에서 서로 흐르는 강들 사이의 거리들이 주어진다.(북쪽부터)

각각의 거리는 27km를 넘지않는다.

출력

비행에 필요한 꿀통의(최저 자금) 수를 출력하라.

예제 입력

2 1
1

예제 출력

1

예제 입력 2

10 10
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2

예제 출력 2

26

예제 입력 3

1 1

예제 출력 3

0

힌트