개조된 트립
시간 제한1초메모리 제한512 MB
각 노드의 접근 빈도와 수정 비용 K가 주어질 때, 일부 우선순위를 바꿔 가중 깊이 합과 수정 비용의 합이 최소가 되도록 트리 모양을 정한다.
문제
특별한 종류의 이진 탐색 트리가 주어진다. 정의에 따르면, 이진 탐색 트리의 임의의 노드의 키는 왼쪽 자식의 키보다 엄격히 크고 오른쪽 자식의 키보다 엄격히 작다.
한편, 이진 탐색 트리의 각 노드는 우선순위를 가지며, 각 노드의 우선순위는 자식의 우선순위보다 엄격히 작다.
트리에 있는 모든 노드의 키는 서로 다르고, 모든 노드의 우선순위도 서로 다르다는 것이 알려져 있다. 여기서 흥미로운 결론에 도달한다. 트리에 있는 모든 노드의 키와 우선순위를 알면 트리의 구조도 결정할 수 있다. 이 트리를 우선순위가 커지는 순서로 모든 노드를 삽입해 만든 트리로 볼 수 있기 때문이다. 이때 이진 탐색 트리 노드는 키로 비교한다.
트리에서 노드의 깊이는 루트 노드로부터의 거리에 1을 더한 값으로 정의한다. 따라서 루트 노드의 깊이는 1이다.
노드는 키와 우선순위 외에도 접근 빈도를 가진다. 노드의 트리 내 접근 비용은 접근 빈도에 깊이를 곱한 값으로 정의한다. 트리 전체의 접근 비용은 모든 노드의 접근 비용의 합으로 정의한다.
이제 각 노드의 키, 우선순위, 접근 빈도가 주어질 때, 여러 노드의 우선순위를 바꿀 수 있으며 우선순위를 바꾼 노드마다 수정 비용 K가 추가로 든다. 노드의 우선순위는 임의의 실수로 바꿀 수 있지만, 바꾼 뒤에도 모든 노드의 우선순위가 서로 달라야 한다. 구해야 하는 것은 트리 전체의 접근 비용과 총 수정 비용의 합으로 가능한 최솟값이다.
입력
입력의 첫째 줄에 두 정수 N과 K가 주어진다. N은 노드의 수이고 K는 우선순위를 한 번 바꿀 때 드는 수정 비용이다.
다음 줄에 N개의 음이 아닌 정수가 주어지며, 이는 모든 노드의 키다.
다음 줄에 N개의 음이 아닌 정수가 주어지며, 이는 모든 노드의 우선순위다.
다음 줄에 N개의 음이 아닌 정수가 주어지며, 이는 모든 노드의 접근 빈도다.
키, 우선순위, 접근 빈도 중 어느 것도 400000을 넘지 않는다. 같은 줄에서 인접한 두 값은 공백 하나로 구분되며, 줄 끝에 공백은 없다.
출력
트리 전체의 접근 비용과 총 수정 비용의 합으로 가능한 최솟값을 한 줄에 출력한다.
제한
N≤ 70- 1 ≤
K≤ 30000000