Farmer John has built a sand castle! Like all good castles, the walls have crennelations, that nifty pattern of embrasures (gaps) and merlons (filled spaces); see the diagram below. 농부 존은 모래성을 지었다. 모든 훌륭한 성 처럼 벽은 crennelations 을 가지고 있고 embrasures 와 merlons 의 깨꿋한 패턴을 가지고 있다. 아래 그림을 참고 The N (1 <= N <= 25,000) merlons of his castle wall are conveniently numbered 1..N; merlon i has height M_i (1 <= M_i <= 100,000); 성의 N 메르론은 편의상 1..N 개의 번호가 부여되어 있다. i 번째 메르론은 높이 Mi 를 가지고 있다. his merlons often have varying heights, unlike so many.
He wishes to modify the castle design in the following fashion: 그는 성을 다음과 같은 형태로 변경하기를 원한다. he has a list of numbers B_1 through B_N 그는 번호 B_1 에서 B_N 의 리스트를 가진다.(1 <= B_i <= 100,000), and wants to change the merlon heights to those heights B_1, ..., B_N in some order (not necessarily the order given or any other order derived from the data). 그리고 merlon 높이를 B_1,..,B_N 으로 어떤 순서로 바꾸기를 원한다.(
To do this, he has hired some bovine craftsmen to raise and lower the merlons' heights. Craftsmen, of course, cost a lot of money. In particular, they charge FJ a total X (1 <= X <= 100) money per unit height added and Y (1 <= Y <= 100) money per unit height reduced.
FJ would like to know the cheapest possible cost of modifying his sand castle if he picks the best permutation of heights. The answer is guaranteed to fit within a 32-bit signed integer.
Note: about 40% of the test data will have N <= 9, and about 60% will have N <= 18.
Farmer John has built a sand castle! Like all good castles, the walls have crennelations, that nifty pattern of embrasures (gaps) and merlons (filled spaces); see the diagram below. The N (1 <= N <= 25,000) merlons of his castle wall are conveniently numbered 1..N; merlon i has height M_i (1 <= M_i <= 100,000); his merlons often have varying heights, unlike so many.
He wishes to modify the castle design in the following fashion: 그는 성을 다음과 같은 형태로 변경하기를 원한다. he has a list of numbers B_1 through B_N 그는 번호 B_1 에서 B_N 의 리스트를 가진다.(1 <= B_i <= 100,000), and wants to change the merlon heights to those heights B_1, ..., B_N in some order (not necessarily the order given or any other order derived from the data). 그리고 merlon 높이를 B_1,..,B_N 으로 어떤 순서로 바꾸기를 원한다.(
To do this, he has hired some bovine craftsmen to raise and lower the merlons' heights. Craftsmen, of course, cost a lot of money. In particular, they charge FJ a total X (1 <= X <= 100) money per unit height added and Y (1 <= Y <= 100) money per unit height reduced.
FJ would like to know the cheapest possible cost of modifying his sand castle if he picks the best permutation of heights. The answer is guaranteed to fit within a 32-bit signed integer.
Note: about 40% of the test data will have N <= 9, and about 60% will have N <= 18.
입력 3 6 5 3 1 1 2 1 2 출력 11
FJ's castle starts with heights of 3, 1, and 1. He would like to change them so that their heights are 1, 2, and 2, in some order. It costs 6 to add a unit of height and 5 to remove a unit of height.
OUTPUT DETAILS:
FJ reduces the first merlon's height by 1, for a cost of 5 (yielding merlons of heights 2, 1, and 1). He then adds one unit of height to the second merlon for a cost of 6 (yielding merlons of heights 2, 2, and 1).
출처:usaco 2009 March