题目描述

题目译自 XXVI Olimpiada Informatyczna – II etap Gwiazdy

在一个几何完美的银河系中，$n$ 颗星辰沿直线排列，从左至右编号为 $1$ 至 $n$。星际旅行极为便捷，因大部分居民拥有瞬移装置，可瞬间从任意星辰跳转至另一星辰。

Bajtalina 居住在编号为 $s$ 的星辰，她刚购置了一台瞬移装置，计划通过 $n-1$ 次瞬移，恰好访问每颗星辰一次（星辰 $s$ 视为已访问）。她希望以最小的能量消耗完成旅程，因装置电池充电成本高昂。

然而，能量消耗依瞬移方向（向左至编号较小的星辰，或向右至编号较大的星辰）及已完成的瞬移次数而变化无常。Bajtalina 在装置说明书中查到能量消耗规则：第 $i$ $(1 \leq i \leq n-1)$ 次瞬移的成本为 $l_i$（向左）或 $r_i$（向右）。

你的任务是帮助 Bajtalina 找到最节能的访问路径。

输入格式

第一行包含两个整数 $n, s$ $(n \geq 2, 1 \leq s \leq n)$，分别表示星辰数量和 Bajtalina 居住的星辰编号。

接下来的 $n-1$ 行描述瞬移成本，第 $i$ 行包含两个整数 $l_i, r_i$ $(0 \leq l_i, r_i \leq 10^6)$，表示第 $i$ 次瞬移向左或向右的成本。

输出格式

第一行输出一个整数，表示完成所有瞬移的最小总成本。

第二行输出 $n$ 个互不相同的整数（范围 $[1, n]$），表示星辰的访问顺序（首数必须为 $s$）。若存在多种最优路径，可输出任意一种。

4 2
5 3
4 6
2 2

9
2 4 1 3

Bajtalina 从编号 $2$ 的星辰开始。第一次瞬移向右（至星辰 $4$），成本 $r_1=3$。第二次瞬移向左（至星辰 $1$），成本 $l_2=4$。最后一次瞬移至星辰 $3$，成本 $r_3=2$（因 $l_3=r_3$，方向无关）。

总成本为 $3+4+2=9$，为最优解。

附加样例

1. $n=10, s=1$，$l_i=1, r_i=2$（对所有 $i$）。
2. $n=18, s=7$，奇数 $i$：$l_i=i, r_i=i+1$；偶数 $i$：$l_i=i+1, r_i=i$。
3. $n=500, s=250$，奇数 $i$：$l_i=0, r_i=1$；偶数 $i$：$l_i=1, r_i=0$。
4. $n=3000, s=1000$，$l_i=r_i=i$（对所有 $i$）。
5. $n=500000, s=1$，$l_i=i, r_i=500000-i$（对所有 $i$）。

数据范围与提示

详细子任务附加限制及分值如下表所示。

对于子任务 $1,2,3,4,5,7,8$，若仅总成本正确，获得 $50\%$ 的分数。