Se consideră o tablă triunghiulară ale cărei laturi au lungimea n (număr întreg), împărțită în triunghiuri ca în figura de mai jos și se consideră m triunghiuri care au dimensiunile laturilor 1. Pe fiecare latură a unui triunghi mic este înscris un număr.

    Se cere să se așeze triunghiuri mici pe tablă astfel încât:

  • tabla să fie acoperită complet;
  • două laturi alăturate care sigur aparțin la două triunghiuri diferite să aibă înscrise același număr.
  • suma tuturor numerelor înscrise pe laturile triunghiurilor așezate pe tablă să fie maximă.


  • Prima linie a fișierului de intrare LEGO.IN conține valorile n și m, separate printr-un singur spațiu, care reprezintă lungimile celor laturi ale tablei, respectiv numărul de triunghiuri care au lungimile laturilor egale cu 1.
        Fiecare dintre următoarele m linii conține câte trei numere, separate între ele prin spațiu, care reprezintă numerele înscrise pe laturile unui triunghi.

    Fișierul de ieșire LEGO.OUT trebuie să conțină o singură linie pe care se va afla suma tuturor numerelor înscrise pe laturile triunghiurilor așezate pe tablă să fie maximă astfel încât să fie respectate condițiile din enunț.

  • 2 ≤ n ≤ 5;
  • 3 ≤ m ≤ 30;
  • numerele înscrise pe laturile triunghiurilor sunt numere întregi cuprinse între 1 și 100;
  • triunghiurile pot fi rotite in orice directie si oglindite;
  • se garantează existența unei soluții.


  • LEGO.IN
    2 6
    3 7 8
    1 2 3
    1 2 7
    5 2 1
    2 4 4
    4 1 2

    LEGO.OUT
    46