$DP[i][j]=$ 1행에서 $i$개의 가장 작은 수와 2행에서 $j$개의 가장 작은 수를 이용해 만들 수 있는 증가하는 부분 수열의 원소의 최대 합으로 정의합니다.

초깃값은 $DP[0][0]=0$이고, $DP[i][0]$과 $DP[0][j]$는 각각 1행과 2행을 정렬하여 누적합 한 결과와 같습니다.

이제 $DP[i][j]$에서 $DP[i+1][j]$로 전이하는 것을 생각합니다. 이 전이에서는 1행의 $i+1$번째 원소를 현재 1행의 증가 수열에 포함시키는 과정이 들어갑니다. 그러면 총합에는 1행의 $i+1$번째로 작은 수가 더해지는데, 이때 다음의 경우가 발생할 수 있습니다.

• 1행에서 $i+1$번째로 작은 열이 이미 포함되어 있다면 (즉 그 열의 2행의 원소가 $j$번째 이하), 그 열을 맨 뒤로 보냈을 때 2행의 증가 부분 수열에서 그 2행의 원소가 빠지는 것을 고려해야 합니다.
  • 단, 정확히 $j$번째라면 이미 마지막에 와 있으므로 빼지 않아도 됩니다.
• 포함되어 있지 않다면, 2행의 원소는 아직 더해지지 않았고 지금 더할 것도 아니므로 무시하면 됩니다.

$N$이 크지 않지만 시간이 매우 빡빡하기 때문에, 이를 2차원 DP 테이블을 만들어 구현하면 TLE를 받을 수 있습니다. 전이 특성상 1차원 테이블 위에서 전이를 진행할 수 있고, 그 외에 메모리 접근 횟수를 줄이는 여러 상수 최적화를 하면 $\mathcal{O}(N^2)$ 시간 복잡도를 갖는 코드로 통과할 수 있습니다.