Task
Time limit:
1000 ms,
Memory limit:
256 Mb
В ориентированном взвешенном графе вершины пронумерованы числами от 1 до n. Если i<j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле wt(i,j)=(179i+719j) mod 1000 - 500. Определите вес кратчайшего пути, ведущего из вершины 1 в вершину n.
Входные данные
Программа получает на вход одно число n (2≤n≤13000).
Выходные данные
Программа должна вывести единственное целое число - вес кратчайшего пути из вершины 1 в вершину n в описанном графе.