#P5482. tree

    ID: 4485 传统题 1000ms 512MiB 尝试: 34 已通过: 14 难度: 8 上传者: 标签>CF2500提高+/省选-指定流量最小费用流残量增广路树形 DP动态 DP

tree

Description

现在有一棵n个结点的树,对于点i(i>1),它的父亲结点编号为trunc(i/2)。

现在有m只鸟,每只鸟有初始位置pi。树上每个结点有最大容纳量ci,表示这个结点最多能容纳的鸟的数量。

定义移动一只鸟的代价为树上的距离。

现在询问,对于k从1∼m,将前k只鸟移动位置使得满足每个结点上的鸟的个数不大于最大容纳量的最小代价。

Format

Input

第一行两个整数 n,mn,m,满足 1≤n,m≤3×1051\le n,m\le3\times10^5。

第二行 nn 个非负整数 c1,…,cnc_1,\ldots,c_n。本站数据保证 ∑ici≥m\sum_i c_i\ge m,因此每个询问均有可行方案。

第三行 mm 个整数 p1,…,pmp_1,\ldots,p_m,满足 1≤pi≤n1\le p_i\le n。

Output

输出一行,表示对于每个k的最小代价。

Samples

5 4 
0 0 4 1 1
2 4 5 2
1 1 2 4

样例说明

第一只鸟在 2 上,只需移到 4 或 5 即可,代价为 1。 第一、二只鸟在 2,4 上,第一只鸟移到 5,第二只鸟不动,代价为 1。 第一、二、三只鸟在 2, 4, 5 上,第一只鸟移到 3,第二、三只鸟不动,代价为 2。 第一、二、三、四只鸟在 2, 4, 5, 2 上,第一、四只鸟移到 3,第二、三只鸟不动,代价为 4。