Fair - MarisaOJ: Marisa Online Judge

Fair

Time limit: 1000 ms
Memory limit: 256 MB
A fairground has the form of a regular polygon consisting of $n$ vertices, the vertices are numbered from $1$ to $n$ clockwise. The organizer divides the fair area by $n - 3$ dividing lines to obtain $n - 2$ triangular booths, the dividing lines do not intersect inside the polygon, the dividing line $k$ passes through two distinct vertices $i_k,j_k$ $(1 \le k \le n - 3)$. Thus, a booth will have three sides, each side is a polygonal edge or dividing line. To encourage visitors to visit the stalls, the organizer will give prizes worth $t_k$ to visitors when passing through the $k$th dividing line. Alice plans to enter the fairground from a booth whose face is an edge connecting vertices $u$ and vertex $(u \\% n + 1)$ then exit the fairground from a booth whose face is an edge connecting vertices $v$ and vertex $(v \\% n + 1)$. Alice hopes that each booth will be visited no more than once and the total value of the rewards received will be the greatest. Note that $u \neq v$ and the operation $\\%$ is to divide and receive remainder. Requirement: Alice has $q$ assumptions, each assumption described by two integers $u,v$ means that Alice enters from the edge connecting vertex $u$ and vertex $(u \\% n + 1) $ and comes out from the edge connecting vertex $v$ and vertex $(v \\% n + 1)$, for each assumption, help Alice compute the maximum possible total value of the rewards that can be achieved. ### Input - The first line contains two positive integers $n,q$ $(q \le n);$ - The $k$-th line $(1 \le k \le n - 3)$ contains three positive integers $i_k,j_k,t_k$ describing the $k$-th dividing line $(1 \le i_k,j_k \le n$ and$i_k \neq j_k;t_k \le 10^9);$ - The second line $s$ $(1 \le s \le q)$ includes two positive integers $u,v$ describing an assumption. ### Output - Write out $q$ lines, each line contains an integer that is the maximum total value of the rewards that can be achieved. Input: ``` 6 2 2 4 1 2 5 2 2 6 3 1 5 1 2 ``` Output: ``` 3 6 ``` ### Subtask - Subtask 1 (40%) : $n \le 10$ - Subtask 2 (30%) : $n \le 100$ - Subtask 3 (30%) : $n \le 10^5$