Statement

Giorgio has just won a grant for travelling to any foreign university. The round trip will be completely reimbursed, providing it does not involve more than K connections. Giorgio now wants to take profit of this trip to gather the highest possible amount of miles on his Alimpiadi fidelity card. The Alimpiadi company has M unidirectional routes connecting a total of N airports. Each route has a mile value, which could be different to the value of any other route including other ones connecting exactly the same cities. Furthermore, not every airport could be reachable just by taking Alimpiadi flights. What is the maximum amount of miles that Giorgio can gather at most, by taking a round trip made of exactly K flights, starting from and arriving to Torino (city number 0)?