分数: 575 点
问题陈述
给定两个长度的序列 N: A=(A_1,A_2,\ldots,A_N) 和 B=(B_1,B_2,\ldots,B_N).
您可以对序列执行以下两种类型的操作 A 以任意顺序任意次数。
- 分裂 A 在任何位置并自由地重新排列分割序列。每个分割位置的成本为 C。 更正式地说,成本为 (X-1)C,取长度序列 X+1, (i_0,i_1,i_2,\ldots,i_X)\ (0=i_0\lt i_1\lt i_2\lt\cdots\lt i_X=N),以及排列 p of (1,2,\ldots,X),并替换 A 与串联 (A_{i_{p_j-1}+1},A_{i_{p_j-1}+2},\ldots,A_{i_{p_j}}) 按升序排列 j.
- 选择一个整数 k 和任何元素 A,并添加 k 为所选元素的值,成本为 |k|.
找出制造所需的最低总成本 A 和 B 通过执行操作等于。
约束
- 1\leq N\leq22
- 1\leq C\leq10^{15}
- 1\leq A_i\leq10^{15}\ (1\leq i\leq N)
- 1\leq B_i\leq10^{15}\ (1\leq i\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N C A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
输出
打印答案。
示例输入 1
5 1 3 1 4 1 5 9 2 6 5 3
示例输出 1
12
例如,您可以使 A 和 B 通过执行以下操作相同。
- 添加 2 to A_2。它的成本 2,和 A 变为 分别为 (3,3,4,1,5).
- 添加 1 to A_4。它的成本 1,和 A 变为 分别为 (3,3,4,2,5).
- 添加 3 to A_3。它的成本 3,和 A 变为 分别为 (3,3,7,2,5).
- 分裂 A 进入 (3,3) 和 (7,2,5),并交换它们的顺序。它的成本 1,和 A 变为 分别为 (7,2,5,3,3).
- 添加 1 to A_3。它的成本 1,和 A 变为 分别为 (7,2,6,3,3).
- 添加 2 to A_4。它的成本 2,和 A 变为 分别为 (7,2,6,5,3).
- 添加 2 to A_1。它的成本 2,和 A 变为 分别为 (9,2,6,5,3).
产生的总成本为 2+1+3+1+1+2+2=12.
不可能使 A 和 B 等于总成本 11 或更少,因此打印 12.
示例输入 2
5 1000000000 3 1 4 1 5 9 2 6 5 3
示例输出 2
15
例如,您可以使 A 和 B 通过执行以下操作相同。
- 添加 6 to A_1。它的成本 6,和 A 变为 分别为 (9,1,4,1,5).
- 添加 1 to A_2。它的成本 1,和 A 变为 分别为 (9,2,4,1,5).
- 添加 2 to A_3。它的成本 2,和 A 变为 分别为 (9,2,6,1,5).
- 添加 4 to A_4。它的成本 4,和 A 变为 分别为 (9,2,6,5,5).
- 添加 -2 to A_5。它的成本 2,和 A 变为 分别为 (9,2,6,5,3).
产生的总成本为 15.
不可能使 A 和 B 等于总成本 14 或更少,因此打印 15.
示例输入 3
22 467772225675200 814424018890229 837987908732596 281175505732576 405797525366223 319378664987871 305374284356649 519144936694626 316916938328237 590332737480143 506785561790072 945769796193819 365498597798550 5386616044591 672368930784037 478017750715806 340276460237787 176509793332130 2734777402752 677509027289850 250325127275409 260270543315523 103584313625431 720386673780641 77160494100361 540947273460639 255177791002759 969333325196025 477751866935037 369600749728569 466236682780196 343161112138696 541310338013515 42740499599240 165778332156355 618106559852784 16582487395877 591851763813728 221861304303645 982850624742022 728669467505250 337968530842725 746724490610504 61587851254728 451153536869240
示例输出 3
4370668608634071
请注意,输入和答案可能不适合 32\operatorname{bit} 整数。