각 변의 길이가 양의 정수이고 영문자 L 모양인 종이가 주어져 있다. 이 종이를 칼로 여러 번 잘라서 모든 조각이 한 변의 길이가 양의 정수인 정사각형이 되도록 하고자 한다.

칼로 종이를 자르는 규칙은 다음과 같다.

1. 자르는 방향은 수직 또는 수평만 허용된다. 즉, 사선으로는 자를 수 없다.
2. 자르는 도중 칼의 방향을 바꿀 수 없다.
3. 자르는 도중에 칼을 멈출 수 없다. 즉, 일단 어떤 조각을 자르기 시작하면 그 조각이 반드 시 둘로 분리될 때 까지 자른다.
4. 잘려진 조각의 각 변의 길이는 양의 정수이어 야 한다.

위의 규칙에 따라 주어진 L 모양의 종이를 잘라 각 조각이 정사각형이 되도록 하되, 잘려진 조각 개수가 최소가 되도록 하고자 한다.

예를 들어, 각 변의 길이가 아래 왼쪽 그림에서 보인 것과 같은 종이가 주어질 때, 최소 개수의 정사각형 조각을 얻도록 자른 결과를 아래 오른쪽 그림에서 보였다.

L 모양의 종이를 제시한 규칙에 따라 잘랐을 때, 잘려진 조각의 개수가 최소가 되도록 하는 프로그램을 작성하시오.

수행 시간은 2초를 넘을 수 없다. 사용하는 메모리는 128MB를 넘을 수 없다.

입력

출력

입출력 예

입력

8 7 3 2

출력

6

입력

5 3 1 1

출력

3

입력

5 5 1 2

출력

6

출처:koi 고등 32 회 지역본선 3/4