N(1≤N≤40)개의 도미노가 있다. 각 도미노는 직사각형으로, 위와 아래 두 부분으로 나누어져 있다. 각 부분에는 0에서 9까지 한 자리의 십진수가 적혀있다.

도미노를 그림으로 표현하면 아래의 그림과 같으며, 위와 아래에 적힌 숫자를 바꿀 수 있다.

도미노를 늘어놓아서 두 개의 n자리 숫자를 만든다. 예를 들어 5와 2, 3과 4, 4와 1이 적힌 도미노를 아래와 같은 식으로 늘어놓는다면, 생성 되는 수는 534와 241이다. 도미노를 늘어 놓는 순서는 아무렇게나 해도 상관 없다.

이 두 수의 합을 최대로 할 수 있는 도미노의 배치를 찾아서, 그 최대의 합을 출력하는 프로그램을 작성하라.

도미노2 timer 1s memory 64MB

도미노2 1s 64MB