Rallonges audio

Vous souhaitez raccorder votre nouvel ordinateur à l'amplificateur de votre super chaîne hi-fi afin de pouvoir mettre à fond l'album "Wish You Were Here" (du groupe Pink Floyd). Vous espérez que la mélodie des guitares électriques fera venir en vous l'inspiration nécessaire pour résoudre des sujets d'algorithmique.

En même temps, vous souhaitez vous rapprocher le plus possible de la borne wifi par laquelle vous accédez à Internet afin de pouvoir télécharger tous les autres albums des Pink Floyd avec un débit maximal (télécharger légalement, bien sûr). Cette borne wifi est commune à votre immeuble et peut théoriquement vous fournir une très bonne bande passante. Malheureusement, elle se situe un peu loin de chez vous et cela est un facteur limitant votre débit. Vous avez déjà remarqué qu'il vous était possible d'améliorer le débit rien qu'en vous déplaçant de quelques mètres en direction de la borne wifi.

Votre but va donc être de combiner les rallonges audio dont vous disposez afin d'obtenir un maximum de longueur, et pouvoir ainsi écouter de la musique tout en étant aussi près que possible de la borne wifi.

Vous avez à votre disposition un certain nombre de rallonges. Chaque rallonge est caractérisée par sa longueur, et par la nature des connecteurs à ses deux extrémités : chaque connecteur peut être soit mâle, soit femelle. Remarque technique : on ne peut pas connecter des fiches mâles entre elles, ni deux fiches femelles entre elles. Notez enfin que la carte son de votre ordinateur ainsi que l'amplificateur de votre chaîne hi-fi portent tous deux des connecteurs femelles (il faut donc arriver dessus avec des connecteurs mâles).

• 1 <= N <= 1 000, où N est le nombre de rallonges.
• 1 <= L <= 100 000, où L est la longueur d'une rallonge (en millimètres).

• La première ligne de l'entrée contient l'entier N.
• Chacune des N lignes suivantes contient trois entiers séparés par des espaces : C1, C2 et L. C1 et C2 décrivent les connecteurs (1 pour mâle, 0 pour femelle), et L donne la longueur de la rallonge.

Notez que le signal peut passer dans une rallonge dans le sens que l'on veut. Ainsi le signal peut traverser la rallonge de C1 vers C2 ou de C2 vers C1.

Vous devez écrire un seul entier sur la sortie : la distance maximale à laquelle vous pouvez placer votre ordinateur de la chaîne hi-fi tout en lui envoyant le signal musical à travers les rallonges. S'il est impossible de relier les deux appareils avec les rallonges dont vous disposez, affichez -1.

Notez que la seconde rallonge a été retournée par rapport à sa description dans l'entrée. La longueur totale obtenue est 500+1000+3000+800=5300.