City Travel Rewards

Problem Statement

City Travel Rewards Problem Description Jack lives in a city with A tourist places, numbered 1 to A , joined by M one-way roads. Two places may be joined by several different roads, a road may lead from a place back to itself, and some places may have no roads touching them at all. The city has launched a loyalty program. Every road carries a fixed base reward point Z . The j-th time Jack drives along one particular road, that trip pays him max(0, Z - j * (j - 1) / 2) reward points. So the first trip along a road pays Z , the second pays Z - 1 , the third Z - 3 , the fourth Z - 6 , and so on. As soon as the formula would go negative the trip pays 0 , and every later trip along that road also pays 0 . Jack starts at place B . He may drive along any roads he likes, in any order, as many times as he likes, and he may stop whenever he likes. Find the maximum total reward points he can accumulate. Input Format The first line contains two integers A and B - the number of tourist places and t