문제

한국정보기술진흥원에는 명의 스파이가 있습니다. 번 스파이는 시 정각에 출근해서 시 정각에 퇴근하며, 보안 등급 를 갖습니다.

한 스파이는 출근해서 퇴근하기 전까지 자신이 알고 있거나, 알게 된 정보를 출근해 있는 다른 스파이에게 직접 전달할 수 있습니다. 한 스파이의 퇴근 시간이 다른 스파이의 출근 시간과 같다면, 두 스파이는 서로 정보를 직접 전달할 수 없습니다.

번 스파이는 번 스파이에게 최대한 은밀하게 정보를 전달하려 합니다.

번 스파이가 출근하면서 가져온 정보를 스파이들이 서로 잘 전달하여 번 스파이에게 정보가 전달되는 각 경우를 시나리오라고 합시다. 각 시나리오의 안전도는 전달 중에 정보를 알게 된 모든 스파이의 보안 등급의 최솟값입니다.

는 가능한 모든 시나리오의 안전도의 최댓값으로 정의됩니다. 만약 가능한 시나리오가 없다면 입니다.

인 모든 , 에 대해 의 합을 구해주세요!

제한

서브태스크

입력

첫 번째 줄에 스파이의 수 이 주어집니다,

이후 개의 줄에 걸쳐 스파이들의 정보 가 공백을 사이에 두고 주어집니다.

출력

첫 번째 줄에 인 모든 , 에 대해 의 합을 구해 출력합니다.

노트

예제 1의 경우, 모든 스파이의 보안 등급이 이므로 는 스파이 가 스파이 에게 정보를 전달할 수 있는 경우 , 아닌 경우 이 됩니다. 따라서 모든 ()에 대한 의 값은 다음과 같습니다.

• : 두 스파이가 직접적으로 정보를 전달하면 되므로 입니다.
• : 번 스파이가 번 스파이에게 정보를 전달하고, 번 스파이가 번 스파이에게 정보를 전달하면 됩니다. 따라서 입니다.
• : 두 스파이가 직접적으로 정보를 전달하면 되므로 입니다.
• : 두 스파이가 직접적으로 정보를 전달하면 되므로 입니다.
• : 번 스파이의 출근 시간이 번 스파이의 퇴근 시간 이후이므로 정보를 전달할 방법이 없습니다. 따라서 입니다.
• : 두 스파이가 직접적으로 정보를 전달하면 되므로 입니다.

따라서 를 출력해야 합니다.