{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:20.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/1e1866c0b6c4403e8e2414c827319db9?v\u003d1715793801\" alt\u003d\"/problems/avoidingairports/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003eDavid is looking to book some travel over the world.\n There are \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e countries\n that he can visit, and \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n flights that are available. The \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth flight goes from country\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e to country\n \u003cspan class\u003d\"tex2jax_process\"\u003e$b_ i$\u003c/span\u003e. It departs at time\n \u003cspan class\u003d\"tex2jax_process\"\u003e$s_ i$\u003c/span\u003e, and lands at time\n \u003cspan class\u003d\"tex2jax_process\"\u003e$e_ i$\u003c/span\u003e.\n\n \u003cp\u003eDavid is currently at the airport in country \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, and the current time is\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e, and he would like to\n travel country \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e. He\n does not care about the total amount of time needed to travel,\n but he really hates waiting in the airport. If he waits\n \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e seconds in an airport,\n he gains \u003cspan class\u003d\"tex2jax_process\"\u003e$t^2$\u003c/span\u003e units of\n frustration. Help him find an itinerary that minimizes the sum\n of frustration.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains two space-separated\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le n,m \\le 200\\, 000$\u003c/span\u003e).\u003c/p\u003e\n\n \u003cp\u003eEach of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n lines contains four space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$b_ i$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$s_ i$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$e_ i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le a_ i, b_ i \\le n$\u003c/span\u003e; \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le s_ i \\le e_ i \\le 10^6$\u003c/span\u003e).\u003c/p\u003e\n\n \u003cp\u003eA flight might have the same departure and arrival\n country.\u003c/p\u003e\n\n \u003cp\u003eNo two flights will have the same arrival time, or have the\n same departure time. In addition, no flight will have the same\n arrival time as the departure time of another flight. Finally,\n it is guaranteed that there will always be a way for David to\n arrive at his destination.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003ePrint, on a single line, the minimum sum of frustration.\u003c/p\u003e\n\n \u003ch2\u003eExamples\u003c/h2\u003e\n\n \u003cp\u003eIn the first sample, it is optimal to take this sequence of\n flights:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eFlight \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e. Goes\n from airport \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to\n airport \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e, departing\n at time \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e, arriving\n at time \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eFlight \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e. Goes\n from airport \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e to\n airport \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, departing\n at time \u003cspan class\u003d\"tex2jax_process\"\u003e$9$\u003c/span\u003e, arriving\n at time \u003cspan class\u003d\"tex2jax_process\"\u003e$12$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eFlight \u003cspan class\u003d\"tex2jax_process\"\u003e$7$\u003c/span\u003e. Goes\n from airport \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to\n airport \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e, departing\n at time \u003cspan class\u003d\"tex2jax_process\"\u003e$13$\u003c/span\u003e, arriving\n at time \u003cspan class\u003d\"tex2jax_process\"\u003e$27$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eFlight \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e. Goes\n from airport \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e to\n airport \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e, deparing\n at time \u003cspan class\u003d\"tex2jax_process\"\u003e$28$\u003c/span\u003e, arriving\n at time \u003cspan class\u003d\"tex2jax_process\"\u003e$100$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eThe frustration for each flight is \u003cspan class\u003d\"tex2jax_process\"\u003e$3^2, 1^2, 1^2,$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$1^2$\u003c/span\u003e, respectively. Thus, the total\n frustration is \u003cspan class\u003d\"tex2jax_process\"\u003e$12$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eNote that there is an itinerary that gets David to his\n destination faster. However, that itinerary has a higher total\n frustration.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 8\n1 2 1 10\n2 4 11 16\n2 1 9 12\n3 5 28 100\n1 2 3 8\n4 3 20 21\n1 3 13 27\n3 5 23 24\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e3 5\n1 1 10 20\n1 2 30 40\n1 2 50 60\n1 2 70 80\n2 3 90 95\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1900\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}