평면에 여러 개의 점이 주어져 있다.

이 점들에는 각각 번호가 1 번부터 차례대로 붙어 있다. 그리고 같은 번호의점들은 각각 2 개씩의 쌍으로 준비되어 있다. 따라서 전체점의 수는 반드시 짝수개이다.

우리는 같은 번호를 가진 두 개의 점들 대각선의 꼭지점으로 하는 직사각형으로 연결하고자 한다. 이 직사각형을 연결사각형이라고부른다.

문제는 다음의 세가지 조건을 만족하면서 서로 겹치지 않는 여러개의 연결사각형을 찾아내는 것이다.

• 조건1: 연결사각형은 반드시 같은 번호의 점을 대각선 꼭지점으로 해야 한다. 만일 서로 다른 번호의 점을 직사각형으로 연결하면 안된다.

• 조건2: 각 사각형은 반드시 서로 떨어져 있어야 한다. 그림-1 과 같은 경우는 허용되지 않는다. 그림-2 와 같이 두 연결사각형의 변이나 꼭지점이 서로붙어 있는 경우나 , 그림-3 과 같이 어떤 직사각형이 다른 직 사각형 안에 포함되는 경우도 허용되지 않는다.

  

• 조건3: 연결 사각형을 만들었을 때에 얻는 점수는 그 쌍에 부여된 번호와 같다. 따라서 그림-4 와 같이 연결했을 경우에 얻는 점수는 1+4+5+6=16 점이다.

위의 조건을 만족시키면서 가장 높은 점수를 얻도록 하는 프로그램을 작성하시오. 실행시간은 10 초를 넘을 수 없다.

입력형식

• 첫 줄에는 쌍의 수가 주어진다.
• 그 다음 줄부터는 1 번 부터 순서대로 두점의 좌표가 나온다.

출력형식

입력과 출력의 예

입력 6 2 5 1 3 5 6 3 2 5 2 6 4 7 6 5 8 1 6 5 4 3 7 7 3

출력

3
1 3 4

출처:1998 koi 중등 2번