를 늘릴 때 새로 더해지는 값은 이다. 가 내림차순이므로 각 열에서 더 위에 있는 값을 고르지 않고 아래 값을 고르는 일은 최적해에 필요하지 않다. 따라서 전체 개의 값 중 큰 것 개를 고른 합이 답이다.
어떤 정수 이상인 쌍의 개수는 를 정렬한 뒤 각 에 대해 이분 탐색하여 에 셀 수 있다. 개수가 이상인 가장 큰 를 찾는다. 그 뒤 보다 큰 모든 쌍의 합을 구하고, 부족한 개수만큼 를 더한다. 합은 64비트 정수 범위를 넘을 수 있으므로 128비트 정수를 사용해야 한다.
