【题目描述】： 越越开了一家木工厂，每次运来一根原木（长度为 � L ），木工师傅们（共 � N 人）就会来截取木头，第 � i 个师傅会截取一段长度为 � � a i ​ 或 � � b i ​ 的木料，来完成自己的作品。对于这根原木，每个师傅最多可以截取一次，当然作为老板，越越可以为了减少木料的浪费，让某个师傅，放弃在这根原木上取木料。

你能给出每位师傅如何截取，使得剩下的木料最少吗？

请你给出一个师傅们的截取方案，如果有多个截取方案，请你输出字典序最小的一个方案。

所谓字典序最小的，是指先以第一个师傅截取的长度比，最较小的，如果相等，则以第二个师傅截取的长度比较， ⋯ ⋯ 。

【输入描述】： 第一行两个正整数 � N 和 � L；( 1 ≤ � ≤ 17 1≤N≤17， 1 ≤ � ≤ 1 0 8 1≤L≤10 8 )

以下 � N 行，第 � i 行两个正整数 � � a i ​ 和 � � b i ​ 。( 1 ≤ � � , � � ≤ 1 0 8 1≤a i ​ ,b i ​ ≤10 8 )

【输出描述】： 输出第一行，一个非负整数，表示剩下木料的长度；

第二行 � N 个非负整数，按师傅编号的顺序，给出师傅们的截取方案（字典序最小的）。

【样例输入】： 3 10 3 5 2 6 2 9 Copy 【样例输出】： 1 0 0 9