Receptet

Du har bestämt dig för att laga mat. För att laga maten behöver du $N$ ingredienser. För varje ingrediens vet du hur mycket du redan har hemma, hur mycket du behöver totalt samt kostnaden för en enhet av ingrediensen om du måste köpa den. Du skall alltså köpa den mängd av varje ingrediens som du saknar. Uppgiften är att beräkna kostnaden för att laga maten. Det kommer inte finnas mer än 5 ingredienser.

Indata

Den första raden innehåller ett heltal $1 \le N \le 5$, antalet ingredienser du behöver.

De nästa $N$ raderna beskriver en ingrediens med tre heltal $H, B, K$ (alla mellan $0$ och $500$) som står för hur mycket du har, hur mycket som behövs och hur mycket den kostar per enhet.

Utdata

Ett heltal med den totala kostnaden för ingredienserna.

Poängsättning

Ditt program kommer att testas på tre testfall. Om du klarar två av dessa kommer du att få $50$ poäng. Om du klarar alla tre kommer du att få $100$ poäng.

I två av testfallen är $n \le 15$.

3
10 5 1000
0 4 5
2 5 1

23