시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB398504116.942%

문제

방 바닥을 꾸미려고 한다. 다음과 같이 1×5 크기의 나무 판으로 만든 무한한 패턴의 평면을 생각해보자. 가장 왼쪽 위 좌표는 (0,0)이고, X좌표는 왼쪽에서 오른쪽으로 증가하고, Y좌표는 위에서 아래로 증가한다.

이제 이 패턴에서 방 크기와 맞는 구역을 선택할 것이다. 이때 왼쪽 위의 좌표가 (x1, y1)이고, 오른쪽 아래의 좌표가 (x2, y2)인 직사각형 구역을 선택한다. 자 이제 선택한 구역의 모양을 만들 것이다.

하지만, 근처의 상점에서는 오직 1×5크기의 나무 판만 판다. 따라서, 1×3, 1×2크기의 나무 판은 1×5크기의 나무 판을 적절히 잘라서 만들면 된다. 예를 들어, 1×5를 잘라서 1×3과 1×2를 만들 수 있고, 1×2 2개와 1×1 1개를 만들 수도 있다.

위의 그림은 (x1, y1)이 (8, 5)이고, (x2, y2)가 (20, 16)일 때이다. 23개의 1×5와 6개의 1×2, 5개의 1×1이 필요하다. 따라서 27개의 나무 판을 사면 된다.

x1, y1, x2, y2가 주어질 때 구매해야 하는 나무 판의 개수의 최솟값을 구하는 프로그램을 작성하시오. 필요없는 조각은 버려도 된다.

입력

첫째 줄에 네 정수 x1, y1, x2, y2가 주어진다.

출력

첫째 줄에 구매해야 하는 나무 판 개수의 최솟값을 출력한다.

제한

  • 0 ≤ x1 < x2 ≤ 1,000,000
  • 0 ≤ y1 < y2 ≤ 1,000,000

예제 입력 1

8 5 20 16

예제 출력 1

27

예제 입력 2

0 0 5 5

예제 출력 2

5

예제 입력 3

0 0 10 2

예제 출력 3

5

예제 입력 4

2 2 8 8

예제 출력 4

12

예제 입력 5

0 0 1000000 1000000

예제 출력 5

200000000000

출처