题目描述

题目译自 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$，为最优解。

附加样例

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

数据范围与提示

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

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