Triangolazione di costo minimo di un esagono pesato

Un esagono convesso ha vertici P1, P2, P3, P4, P5, P6 (in ordine) con pesi rispettivi 3, 7, 4, 5, 2, 6.
Una triangolazione lo divide in 4 triangoli mediante diagonali che non si intersecano. Il costo di un triangolo è il prodotto dei pesi dei suoi tre vertici, e il costo di una triangolazione è la somma dei costi dei suoi 4 triangoli.
Qual è il costo minimo di una triangolazione dell'esagono?