小友是公司的文化大使，为了增加团队的凝聚力并激发大家的工作激情，他决定带着大家一起去旅游。

这次旅程包含了$n$个景点，编号1~$n$，每个景点都有一个大众评分。使用一维数组$scores$表示，其中$scores[i]$表示编号为$i$的(1<=i<=n)景点的大众评分。并且每个景点都有一个海拔高度，用一维数组$heights$表示，其中$heights[i]$表示编号为$i$的(1<=n)景点的海拔高度。
由于员工年龄分布比较均匀，体力有限，这次旅程最多游览$m$个景点，并且在连续游览多个景点后必须在某些景点休息。休息景点都是景点后正一块的，通过给定数组$rest$表示。其中$rest[k] = 1$表示编号为$k$的(1<=k<=n)景点需要休息，0表示不需要休息。为了追求更高的视野，只有当景点的海拔高度不低于之前访问的所有景点的海拔时，你才能游览它。

请帮助小友设计一个最优的旅程线路，使得整个旅程当中能够获得最高的大众评分分数，请给出这个最高大众评分，以及旅游线路和休息方案。

输入描述

第一行输入3个整数$n, m$和$r$，含义如题干所述。
第二行输入一个整数数组$scores$数组，表示每个景点的大众评分。
第三行输入一个整数数组$heights$数组，表示每个景点的海拔高度。
第四行输入一个整数数组$rest$数组，表示景点是否需要休息的情况。

输出描述

第一行一个整数表示旅途获得的最高大众评分。
第二行输出一个二维数组$routes$表示最优旅游线路，由景点编号组成。
第三行输出一个二维数组$stop$表示旅途休息方案，其长度和$routes$数组一样，由0和1组成。其中$stop[i] = 1$表示景点$routes[i]$需要休息，0表示不需要休息。

补充说明

• $1 \le n \le 9$
• $0 \le m \le n$
• $0 \le r \le n$
• $0 \le scores[i] < 1000$
• $0 \le heights[i] < 1000$

注意： 如果存在多个最优旅游线路，请给出线路中所有景点编号组成的字符串按字典序最小的方案。例如，共有6个景点，编号分别为1-6，假设其中方案路线3->5->4和方案2->6->1均为最优路线，则方案景点编号组成的字符串"261"字典序小于方案"354"，需要返回方案"261"路线。休息方案如果存在多个，则取该休息方案中所有0和1组成的字符串按字典序最小的方案。例如，假设$stop$数组为[0,0,0]和[0,1,0]均为最优休息方案，则取[0,0,0]作为最优休息方案。

示例1

输入

5 3 2
10 5 12 8 15
2 1 4 3 5
0 1 0 1 0

输出

35
4 3 5
1 0 0

说明

最高评分为35
最优路线为：景点4 -> 景点3 -> 景点5
休息方案为：在景点4休息，景点3和景点5都不休息

示例2

输入

5 4 2
348 508 112 71 493
3 2 786 970 728
1 1 0 1 0

输出

1461
2 1 5 3
0 1 0 0

说明

最高评分为1461
最优路线为：景点2 -> 景点1 -> 景点5 -> 景点3
休息方案为：在景点2不休息，景点1休息，景点5和景点3都不休息