Задача №1994. Форд-Беллман - 2
В ориентированном взвешенном графе вершины пронумерованы числами от 1 до n. Если i<j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле wt(i,j)=(179i+719j) mod 1000 - 500. Определите вес кратчайшего пути, ведущего из вершины 1 в вершину n.
Входные данные
Программа получает на вход одно число n (2≤n≤13000).
Выходные данные
Программа должна вывести единственное целое число - вес кратчайшего пути из вершины 1 в вершину n в описанном графе.
Примеры
Входные данные
2
Выходные данные
117
Входные данные
3
Выходные данные
-164
Сдать: для сдачи задач необходимо войти в систему