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