mccme.ru #1994

##http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=1994#1

TL: 1 sec
ML: 16M

You are given a weighted directed graph. The vertices are enumerated from (1) to (n).
If (i<j),then there is an edge from vertex (i) to vertex (j), the weight of which is
defined by:		wt(i,j) = (179*i+719*j) mod 1000 - 500
Your task is to find the shortest path between the vertex (1) and the vertex (n).

Input
There first line contains one integer (n) (2≤n≤13000)

Output
Write the shortest path weight.

Sample test(s):
input:
2
output:
117
input:
3
output:
-164