# Tricky Triangularization

**Computer Science**Level 4

A *root path* is a path in a triangular lattice which contains exactly one vertex in each row.

What is the maximum sum of the numbers on the vertices of a root path in this lattice of 500 rows?

**Details and Assumptions**

- For eg, in the following lattice, the vertex \(\color{blue}{5}\) can only be connected to the \(\color{red}{\text{red}}\) vertices in a root path.

\[1\\\color{red}{2}\quad\color{red}{3}\\4\quad\color{blue} {5}\quad6\\7\quad\color{red}{8}\quad\color{red}{9}\quad 1\] - All neighbouring vertices must be connected with an edge.
Explicit example of maximum sum root path, highlighted in red:

\[\color{red}{3}\\ \color{red}{7}\quad 4\\ 2\quad \color{red}{4}\quad 6\\ 8\quad 5\quad \color{red}{9}\quad 3\]

Bruteforce is not the best idea because \(2^{499}\) paths exist. An efficient solution can find the answer well under a second.