{"problem":{"name":"Train Service Planning","description":{"content":"There is a railroad in Takahashi Kingdom. The railroad consists of $N$ sections, numbered $1$, $2$, ..., $N$, and $N+1$ stations, numbered $0$, $1$, ..., $N$. Section $i$ directly connects the station","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc011_f"},"statements":[{"statement_type":"Markdown","content":"There is a railroad in Takahashi Kingdom. The railroad consists of $N$ sections, numbered $1$, $2$, ..., $N$, and $N+1$ stations, numbered $0$, $1$, ..., $N$. Section $i$ directly connects the stations $i-1$ and $i$. A train takes exactly $A_i$ minutes to run through section $i$, regardless of direction. Each of the $N$ sections is either single-tracked over the whole length, or double-tracked over the whole length. If $B_i = 1$, section $i$ is single-tracked; if $B_i = 2$, section $i$ is double-tracked. Two trains running in opposite directions can cross each other on a double-tracked section, but not on a single-tracked section. Trains can also cross each other at a station.\nSnuke is creating the timetable for this railroad. In this timetable, the trains on the railroad run every $K$ minutes, as shown in the following figure. Here, bold lines represent the positions of trains running on the railroad. (See Sample 1 for clarification.)\n![image](https://atcoder.jp/img/agc011/a5c221ce77ab6ee8aee48e75a4e5c969.png)\nWhen creating such a timetable, find the minimum sum of the amount of time required for a train to depart station $0$ and reach station $N$, and the amount of time required for a train to depart station $N$ and reach station $0$. It can be proved that, if there exists a timetable satisfying the conditions in this problem, this minimum sum is always an integer.\nFormally, the times at which trains arrive and depart must satisfy the following:\n\n*   Each train either departs station $0$ and is bound for station $N$, or departs station $N$ and is bound for station $0$.\n*   Each train takes exactly $A_i$ minutes to run through section $i$. For example, if a train bound for station $N$ departs station $i-1$ at time $t$, the train arrives at station $i$ exactly at time $t+A_i$.\n*   Assume that a train bound for station $N$ arrives at a station at time $s$, and departs the station at time $t$. Then, the next train bound for station $N$ arrives at the station at time $s+K$, and departs the station at time $t+K$. Additionally, the previous train bound for station $N$ arrives at the station at time $s-K$, and departs the station at time $t-K$. This must also be true for trains bound for station $0$.\n*   Trains running in opposite directions must not be running on the same single-tracked section (except the stations at both ends) at the same time.\n\n## Constraints\n\n*   $1 \\leq N \\leq 100000$\n*   $1 \\leq K \\leq 10^9$\n*   $1 \\leq A_i \\leq 10^9$\n*   $A_i$ is an integer.\n*   $B_i$ is either $1$ or $2$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $B_1$\n$A_2$ $B_2$\n:\n$A_N$ $B_N$\n\n## Partial Score\n\n*   In the test set worth $500$ points, all the sections are single-tracked. That is, $B_i = 1$.\n*   In the test set worth another $500$ points, $N \\leq 200$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc011_f","tags":[],"sample_group":[["3 10\n4 1\n3 1\n4 1","26\n\nFor example, the sum of the amount of time in question will be $26$ minutes in the following timetable:\n![image](https://atcoder.jp/img/agc011/a5c221ce77ab6ee8aee48e75a4e5c969.png)\nIn this timetable, the train represented by the red line departs station $0$ at time $0$, arrives at station $1$ at time $4$, departs station $1$ at time $5$, arrives at station $2$ at time $8$, and so on."],["1 10\n10 1","\\-1"],["6 4\n1 1\n1 1\n1 1\n1 1\n1 1\n1 1","12"],["20 987654321\n129662684 2\n162021979 1\n458437539 1\n319670097 2\n202863355 1\n112218745 1\n348732033 1\n323036578 1\n382398703 1\n55854389 1\n283445191 1\n151300613 1\n693338042 2\n191178308 2\n386707193 1\n204580036 1\n335134457 1\n122253639 1\n824646518 2\n902554792 2","14829091348"]],"created_at":"2026-03-03 11:01:13"}}