Minimizing Lazy Segment Tree Cost

Consider a directed graph with \(n\) vertices and \(m\) edges. Each vertex represents a star in the deep sky, and each directed edge has an associated weight given by an ordered triple \((l_i, r_i, w_i)\). There is no weight on vertices and the graph may contain self loops or multiple edges. It is guaranteed that there is at least one path from a given start vertex \(s\) to a target vertex \(t\).

You are also given a lazy segment tree that is built on an array \(a\) of length \(k\), initially filled with zeros. When you traverse an edge with parameters \((l_i, r_i, w_i)\), you perform an update on the segment tree by adding \(w_i\) to every element in the interval \([l_i, r_i]\) using the update algorithm described below.

The pseudo-code for the segment tree update is:

$$ \begin{array}{l}\hline\hline\\ \textbf{Algorithm: }\;SegTree\\\hline \begin{array}{rl} 1& \mathbf{Input.}\ \text{An array } a \text{ of length } k \text{, initially all } 0\\ 2& \mathbf{Output.}\ \text{The updated } a \text{ after a series of range additions}\\ 3& \mathbf{Method:}\\ 4& \mathrm{Add}(L,R,x)\\ 5& \quad\mathrm{Add0}(L,R,x,root,1,k)\\ 6& \mathrm{Add0}(L,R,x,u,l,r)\\ 7& \quad\mathbf{if}\; L \le l \;\mathbf{and}\; r \le R\\ 8& \quad\quad \mathrm{tag}(u) \gets \mathrm{tag}(u) + x\\ 9& \quad\quad \mathbf{return}\\ 10& \quad mid \gets \lfloor\frac{l+r}{2}\rfloor\\ 11& \quad \mathrm{tag}(\mathrm{lson}(u)) \gets \mathrm{tag}(\mathrm{lson}(u)) + \mathrm{tag}(u)\\ 12& \quad \mathrm{tag}(\mathrm{rson}(u)) \gets \mathrm{tag}(\mathrm{rson}(u)) + \mathrm{tag}(u)\\ 13& \quad \mathrm{tag}(u) \gets 0\\ 14& \quad\mathbf{if}\; L \le mid\\ 15& \quad\quad \mathrm{Add0}(L,R,x,\mathrm{lson}(u),l,mid)\\ 16& \quad\mathbf{if}\; mid < R\\ 17& \quad\quad \mathrm{Add0}(L,R,x,\mathrm{rson}(u),mid+1,r)\\ \end{array}\\\hline\hline \end{array} $$

Each update on an edge \((l_i, r_i, w_i)\) adds lazy tag values to those nodes in the segment tree that form the minimal cover of the interval \([l_i, r_i]\). Let \(f(l_i, r_i)\) denote the number of segment tree nodes that receive a direct update in this minimal cover. Thus, the cost incurred by traversing that edge is defined as:

$$ \text{cost of edge } i = w_i \times f(l_i, r_i). $$

Your task is to find a path from vertex \(s\) to vertex \(t\) such that the total cost (the sum of the costs of the traversed edges) is minimized. Output this minimum total cost.

inputFormat

The first line contains five integers \(n\), \(m\), \(k\), \(s\), and \(t\), representing the number of vertices, the number of edges, the length of the segment tree array, the starting vertex, and the target vertex respectively.

Then follow \(m\) lines. Each line contains five integers \(u\), \(v\), \(l\), \(r\), and \(w\), representing a directed edge from vertex \(u\) to vertex \(v\) with parameters \(l\), \(r\), and \(w\).

outputFormat

Output a single integer: the minimum possible total cost to travel from vertex \(s\) to vertex \(t\) according to the above rules.

sample

3 3 4 1 3
1 2 1 4 1
2 3 1 3 2
1 3 2 4 3

5