There are N cities $($numbered from $1$ to N$,$ from left to right$)$ arranged in a row and N$-1$ one$-$way roads between them: $1->2->3->->$N$1-$N

The government has a plan to build M new roads. The roads will be built one by one. The Kith road will connect the A$[$K$]-$th city with the B$[$K$]-$th city $($roads are numbered from $0$ to M$-1).$ Each road will lead from the left to the right, from a city with a smaller number to a city with a larger number. No two roads will intersect. Formally, there will be no

two roads AB and CD$,$ such that A C$6->7,$ and its length is $5.$ After building the second road $(5-7),$ the shortest path from home to school is: $124-5-7,$ and its length is $4.$ After building the third road $(14),$ the shortest path from home to school is: $1457,$ and its length is $3$

$2.$ Given X$=[1,1,1],$ Y $=[7,4,6)$ and N $=7,$ the function should return $[1,1,11].$ After building the first road $(17),$ the length of the shortest path from home to school is $1.$ The roads built subsequently do not improve the result

$3.$ Given x $=130,50,401,$ Y $[40,60,50)$ and N$-100,$ the function should return $(90,81\mathrm{.}72].$ Each new road shortens the distance from home to school by $9.$