33OJ
登录 注册

#S0004. 小 z 的快递车

小 z 的快递车

题目描述

小 Z 的仓库在一条笔直街道的位置 00。街道有正、负两个方向,第 ii 件包裹要送到位置 xix_i,其中 xi≠0x_i\ne 0。若 xi>0x_i>0,表示在仓库右侧;若 xi<0x_i<0,表示在仓库左侧。

小 Z 的快递车每次最多装 KK 件包裹。每一趟,他从仓库出发,装上若干件包裹,沿街把这些包裹送到对应位置,最后回到仓库。每件包裹只需要送一次。

求送完所有包裹并回到仓库所需的最小总路程。

输入格式

第一行两个整数 n,Kn,K,分别表示包裹数量和每趟最多装的包裹数量。

第二行 nn 个整数 x1,x2,…,xnx_1,x_2,\dots,x_n,表示每件包裹的目的地位置,保证 xi≠0x_i\ne 0。

输出格式

输出一个整数,表示最小总路程。

样例输入

6 2
-5 -3 -1 2 4 6

样例输出

28

样例解释

正方向包裹位置为 2,4,62,4,6。按从远到近排序为 6,4,26,4,2,每 22 件一趟:

  • 一趟送 6,46,4,最远为 66,路程 2×6=122\times 6=12;
  • 一趟送 22,最远为 22,路程 2×2=42\times 2=4。

正方向总路程为 1616。

负方向包裹位置为 −5,−3,−1-5,-3,-1,到仓库距离分别为 5,3,15,3,1。按从远到近排序为 5,3,15,3,1,每 22 件一趟:

  • 一趟送距离 5,35,3,最远为 55,路程 2×5=102\times 5=10;
  • 一趟送距离 11,最远为 11,路程 2×1=22\times 1=2。

负方向总路程为 1212。

总路程为 16+12=2816+12=28。

数据范围

对于 100%100\% 的数据:

1≤K≤n≤2×1051\le K\le n\le 2\times 10^5

1≤∣xi∣≤1091\le |x_i|\le 10^9