{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it : the road length and the toll that needs to be paid for the road (expressed in the number of coins). \r\u003cbr\u003eBob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash. \r\u003cbr\u003e\r\u003cbr\u003eWe want to help Bob to find \u003cb\u003ethe shortest path\u003c/b\u003e from the city 1 to the city N \u003cb\u003ethat he can afford\u003c/b\u003e with the amount of money he has. \r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains the integer K, 0 \u0026lt;\u003d K \u0026lt;\u003d 10000, maximum number of coins that Bob can spend on his way. \r\u003cbr\u003eThe second line contains the integer N, 2 \u0026lt;\u003d N \u0026lt;\u003d 100, the total number of cities. \r\u003cbr\u003e\r\u003cbr\u003eThe third line contains the integer R, 1 \u0026lt;\u003d R \u0026lt;\u003d 10000, the total number of roads. \r\u003cbr\u003e\r\u003cbr\u003eEach of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters : \r\u003cbr\u003e\u003cul\u003e\u003cli\u003eS is the source city, 1 \u0026lt;\u003d S \u0026lt;\u003d N \r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eD is the destination city, 1 \u0026lt;\u003d D \u0026lt;\u003d N \r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eL is the road length, 1 \u0026lt;\u003d L \u0026lt;\u003d 100 \r\u003cbr\u003e\u003c/li\u003e\u003cli\u003eT is the toll (expressed in the number of coins), 0 \u0026lt;\u003d T \u0026lt;\u003d100\u003c/li\u003e\u003c/ul\u003e\r\u003cbr\u003eNotice that different roads may have the same source and destination cities. "}},{"title":"Output","value":{"format":"HTML","content":"The first and the only line of the output should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins. \r\u003cbr\u003eIf such path does not exist, only number -1 should be written to the output. \r\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n6\r\n7\r\n1 2 2 3\r\n2 4 3 3\r\n3 4 2 4\r\n1 3 4 1\r\n4 6 2 1\r\n3 5 2 0\r\n5 4 3 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}