G - Cut and Reorder Editorial /

Time Limit: 2.8 sec / Memory Limit: 512 MB

配点 : 575 点

問題文

長さ N の数列 A=(A _ 1,A _ 2,\ldots,A _ N),B=(B _ 1,B _ 2,\ldots,B _ N) が与えられます。

あなたは、数列 A に対して次の 2 種類の操作を好きな順番で好きな回数行うことができます。

  • A を好きな位置で分割し、分割された列を自由に並べ替える。分割した位置 1 つにつきコストが 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) と (1,2,\ldots,X) の順列 p を自由にとり、(A _ {i _ {p _ j-1}+1},A _ {i _ {p _ j-1}+2},\ldots,A _ {i _ {p _ j}}) を j の昇順に連結したものを新しい A とする。
  • 整数 k と A の好きな要素を 1 つ選び、選んだ要素の値に 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 を等しくすることができます。

  • A _ 2 に 2 を加える。コストが 2 かかり、A=(3,3,4,1,5) となる。
  • A _ 4 に 1 を加える。コストが 1 かかり、A=(3,3,4,2,5) となる。
  • A _ 3 に 3 を加える。コストが 3 かかり、A=(3,3,7,2,5) となる。
  • A を (3,3) と (7,2,5) に分割し、順番を入れ替える。コストが 1 かかり、A=(7,2,5,3,3) となる。
  • A _ 3 に 1 を加える。コストが 1 かかり、A=(7,2,6,3,3) となる。
  • A _ 4 に 2 を加える。コストが 2 かかり、A=(7,2,6,5,3) となる。
  • A _ 1 に 2 を加える。コストが 2 かかり、A=(9,2,6,5,3) となる。

かかるコストの合計は 2+1+3+1+1+2+2=12 となります。

コストの合計を 11 以下にして A と B を等しくすることはできないため、12 と出力してください。

入力例 2

5 1000000000
3 1 4 1 5
9 2 6 5 3

出力例 2

15

例えば、次のように操作をすることで A と B を等しくすることができます。

  • A _ 1 に 6 を加える。コストが 6 かかり、A=(9,1,4,1,5) となる。
  • A _ 2 に 1 を加える。コストが 1 かかり、A=(9,2,4,1,5) となる。
  • A _ 3 に 2 を加える。コストが 2 かかり、A=(9,2,6,1,5) となる。
  • A _ 4 に 4 を加える。コストが 4 かかり、A=(9,2,6,5,5) となる。
  • A _ 5 に -2 を加える。コストが 2 かかり、A=(9,2,6,5,3) となる。

かかるコストの合計は 15 となります。

コストの合計を 14 以下にして A と B を等しくすることはできないため、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} 整数に収まらない場合があります。

Score : 575 points

Problem Statement

You are given two sequences of length N: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You can perform the following two types of operations on the sequence A any number of times in any order.

  • Split A at any positions and freely rearrange the split sequences. Each split position incurs a cost of C. More formally, at a cost of (X-1)C, take a sequence of length 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), and a permutation p of (1,2,\ldots,X), and replace A with the concatenation of (A_{i_{p_j-1}+1},A_{i_{p_j-1}+2},\ldots,A_{i_{p_j}}) in ascending order of j.
  • Choose an integer k and any element of A, and add k to the value of the chosen element, for a cost of |k|.

Find the minimum total cost required to make A and B equal by performing the operations.

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N C
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Output

Print the answer.

Sample Input 1

5 1
3 1 4 1 5
9 2 6 5 3

Sample Output 1

12

For example, you can make A and B equal by performing the following operations.

  • Add 2 to A_2. It costs 2, and A becomes (3,3,4,1,5).
  • Add 1 to A_4. It costs 1, and A becomes (3,3,4,2,5).
  • Add 3 to A_3. It costs 3, and A becomes (3,3,7,2,5).
  • Split A into (3,3) and (7,2,5), and swap their order. It costs 1, and A becomes (7,2,5,3,3).
  • Add 1 to A_3. It costs 1, and A becomes (7,2,6,3,3).
  • Add 2 to A_4. It costs 2, and A becomes (7,2,6,5,3).
  • Add 2 to A_1. It costs 2, and A becomes (9,2,6,5,3).

The total cost incurred is 2+1+3+1+1+2+2=12.

It is impossible to make A and B equal with a total cost of 11 or less, so print 12.

Sample Input 2

5 1000000000
3 1 4 1 5
9 2 6 5 3

Sample Output 2

15

For example, you can make A and B equal by performing the following operations.

  • Add 6 to A_1. It costs 6, and A becomes (9,1,4,1,5).
  • Add 1 to A_2. It costs 1, and A becomes (9,2,4,1,5).
  • Add 2 to A_3. It costs 2, and A becomes (9,2,6,1,5).
  • Add 4 to A_4. It costs 4, and A becomes (9,2,6,5,5).
  • Add -2 to A_5. It costs 2, and A becomes (9,2,6,5,3).

The total cost incurred is 15.

It is impossible to make A and B equal with a total cost of 14 or less, so print 15.

Sample Input 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

Sample Output 3

4370668608634071

Note that the input and the answer may not fit into a 32\operatorname{bit} integer.