最近做了一套贪心专题，是时候总结一下了，下面附上题目和思路，具体实现附上链接。

题目地址：贪心1 点击打开链接      密码：LDUACM         

        贪心2点击打开链接        密码：lduacm

贪心

A题  51nod 1449

题目链接： 点击打开链接
1449 砝码称重 题目来源：  CodeForces 基准时间限制：1 秒 空间限制：131072 KB 分值: 40  难度：4级算法题

现在有好多种砝码，他们的重量是  w0,w1,w2,...   每种各一个。问用这些砝码能不能表示一个重量为m的东西。

样例解释：可以将重物和3放到一个托盘中，9和1放到另外一个托盘中。

Input

单组测试数据。
第一行有两个整数w,m (2 ≤ w ≤ 10^9, 1 ≤ m ≤ 10^9)。

Output

如果能，输出YES，否则输出NO。

Input示例

3 7

Output示例

YES

进制转换问题，将物体重量转换成一段0—1的串，再去进行判断。 详细题解： 点击打开链接

B  HDU　1009

题目链接： 点击打开链接

FatMouse' Trade

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 77403    Accepted Submission(s): 26562


Problem Description FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

Input The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.

Output For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

Sample Input

   5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

Sample Output

   13.333
31.500

按照花费和得到的比值进行排序，从大往小进行遍历即可。 详细题解： 点击打开链接

C  HDU　1049

题目链接： 点击打开链接

Climbing Worm

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19538    Accepted Submission(s): 13287


Problem Description An inch worm is at the bottom of a well n inches deep. It has enough energy to climb u inches every minute, but then has to rest a minute before climbing again. During the rest, it slips down d inches. The process of climbing and resting then repeats. How long before the worm climbs out of the well? We'll always count a portion of a minute as a whole minute and if the worm just reaches the top of the well at the end of its climbing, we'll assume the worm makes it out.

Input There will be multiple problem instances. Each line will contain 3 positive integers n, u and d. These give the values mentioned in the paragraph above. Furthermore, you may assume d < u and n < 100. A value of n = 0 indicates end of output.

Output Each input instance should generate a single integer on a line, indicating the number of minutes it takes for the worm to climb out of the well.

Sample Input

   10 2 1
20 3 1
0 0 0

Sample Output

   17
19

这种水题，不解释了吧。

D    HDU　1050

题目链接： 点击打开链接

Moving Tables

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 35471    Accepted Submission(s): 11681


Problem Description The famous ACM (Advanced Computer Maker) Company has rented a floor of a building whose shape is in the following figure.



The floor has 200 rooms each on the north side and south side along the corridor. Recently the Company made a plan to reform its system. The reform includes moving a lot of tables between rooms. Because the corridor is narrow and all the tables are big, only one table can pass through the corridor. Some plan is needed to make the moving efficient. The manager figured out the following plan: Moving a table from a room to another room can be done within 10 minutes. When moving a table from room i to room j, the part of the corridor between the front of room i and the front of room j is used. So, during each 10 minutes, several moving between two rooms not sharing the same part of the corridor will be done simultaneously. To make it clear the manager illustrated the possible cases and impossible cases of simultaneous moving.



For each room, at most one table will be either moved in or moved out. Now, the manager seeks out a method to minimize the time to move all the tables. Your job is to write a program to solve the manager’s problem.

Input The input consists of T test cases. The number of test cases ) (T is given in the first line of the input. Each test case begins with a line containing an integer N , 1<=N<=200 , that represents the number of tables to move. Each of the following N lines contains two positive integers s and t, representing that a table is to move from room number s to room number t (each room number appears at most once in the N lines). From the N+3-rd line, the remaining test cases are listed in the same manner as above.

Output The output should contain the minimum time in minutes to complete the moving, one per line.

Sample Input

    3 
4 
10 20 
30 40 
50 60 
70 80 
2 
1 3 
2 200 
3 
10 100 
20 80 
30 50 

Sample Output

    10
20
30

首先要把对面的房间进行合并，然后对时间进行排序，如果时间有重叠，则在所在区间进行++，然后找到次数最多的区间，输出。题目想法跟E题一样。 详细题解： 点击打开链接

E   HDU  1051

题目链接： 点击打开链接

Wooden Sticks

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 21402    Accepted Submission(s): 8636


Problem Description There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l<=l' and w<=w'. Otherwise, it will need 1 minute for setup.

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

Input The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains n 2 positive integers l1, w1, l2, w2, ..., ln, wn, each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

Output The output should contain the minimum setup time in minutes, one per line.

Sample Input

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

Sample Output

   2
1
3

题目同上一次一样，对长度进行排序，然后进行遍历，用数组进行标记，遍历一遍，把所有的长度重量大于第一的进行标记，然后再去搜下一个没被标记的，以此类推。 详细题解： 点击打开链接

F 51nod  1625

1625 夹克爷发红包 基准时间限制：1 秒 空间限制：131072 KB 分值: 20  难度：3级算法题 在公司年会上，做为互联网巨头51nod掌门人的夹克老爷当然不会放过任何发红包的机会。
现场有n排m列观众，夹克老爷会为每一名观众送出普通现金红包，每个红包内金额随机。
接下来，夹克老爷又送出 最多k组高级红包，每 组高级红包会同时给一排或一列的人派发 ,每 个高级红包的金额皆为x。
派发高级红包时，普通红包将会强制收回。同时，每个人只能得到一个高级红包。（好小气！）
现在求一种派发高级红包的策略，使得现场观众获得的红包总金额最大。 Input

第一行为n, m, x, k四个整数。1 <= n <= 10, 1 <= m <= 200
1 <= x <= 10^9，0 <= k <= n + m接下来为一个n * m的矩阵，代表每个观众获得的普通红包的金额。普通红包的金额取值范围为1 <= y <= 10^9

Output

输出一个整数，代表现场观众能获得的最大红包总金额

Input示例

3 4 1 5
10 5 7 2
10 5 10 8
3 9 5 4

Output示例

78

建议直接看题解。 详细题解： 点击打开链接

G  HDU   2111

题目链接： 点击打开链接

Saving HDU

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11608    Accepted Submission(s): 5280


Problem Description 话说上回讲到海东集团面临内外交困，公司的元老也只剩下XHD夫妇二人了。显然，作为多年拼搏的商人，XHD不会坐以待毙的。
  一天，当他正在苦思冥想解困良策的时候，突然想到了自己的传家宝，那是公司成立的时候，父亲作为贺礼送来的一个锦囊，徐父当时交代，不到万不得已的时候，不要打开它。“现在不正是最需要的时候吗？”，一边想，XHD一边找到了这个精心保管的锦囊，打开一看，里面只有一句话“杭城北麓千人洞有宝”。
  二话不说，XHD拿起一个大口袋就出发了，这个千人洞他是知道的，小的时候，爸爸曾经带他来过这个隐蔽的路口，并告诉他，这是千人洞。他现在才明白爸爸当初这句话的含义。
  尽管有点印象，XHD还是花了很大的精力才找到这个异常隐蔽的洞口，走进一看，几乎惊呆了，真的是眼花缭乱！不过尽管宝贝的种类不少，但是每种宝贝的量并不多，当然，每种宝贝单位体积的价格也不一样，为了挽救HDU，现在请你帮忙尽快计算出来XHD最多能带回多少价值的宝贝？（假设宝贝可以分割，分割后的价值和对应的体积成正比）

Input 输入包含多个测试实例，每个实例的第一行是两个整数v和n(v,n<100)，分别表示口袋的容量和宝贝的种类，接着的n行每行包含2个整数pi和mi(0
Output 对于每个测试实例，请输出XHD最多能取回多少价值的宝贝，每个实例的输出占一行。

Sample Input

   2 2
3 1
2 3
0

Sample Output

   5

先把单价排序，然后依次取出单价由高到底的个数（总体积一直在减少到0停止），计算总价值。注意排序。

详细题解：点击打开链接

H HDU 1052

题目链接： 点击打开链接

Tian Ji -- The Horse Racing

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 30124    Accepted Submission(s): 9070 Problem Description Here is a famous story in Chinese history."That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others.""Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser.""Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian's. As a result, each time the king takes six hundred silver dollars from Tian.""Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match.""It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king's regular, and his super beat the king's plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China?" Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian's horses on one side, and the king's horses on the other. Whenever one of Tian's horses can beat one from the king, we draw an edge between them, meaning we wish to establish this pair. Then, the problem of winning as many rounds as possible is just to find the maximum matching in this graph. If there are ties, the problem becomes more complicated, he needs to assign weights 0, 1, or -1 to all the possible edges, and find a maximum weighted perfect matching...However, the horse racing problem is a very special case of bipartite matching. The graph is decided by the speed of the horses --- a vertex of higher speed always beat a vertex of lower speed. In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.In this problem, you are asked to write a program to solve this special case of matching problem. Input The input consists of up to 50 test cases. Each case starts with a positive integer n (n <= 1000) on the first line, which is the number of horses on each side. The next n integers on the second line are the speeds of Tian’s horses. Then the next n integers on the third line are the speeds of the king’s horses. The input ends with a line that has a single 0 after the last test case. Output For each input case, output a line containing a single number, which is the maximum money Tian Ji will get, in silver dollars. Sample Input

   3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0

Sample Output

   200
0
0

典型贪心题目，先进行排序，若田忌的马快于同等位置的马就让他赢，否则就让他输给齐王最快的马，注意平等的时候，需要另加判断。三个循环，平等时再嵌套一个。 详细题解： 点击打开链接

贪心2

A   HDU  4864

题目链接： 点击打开链接

Task

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7196    Accepted Submission(s): 1896


Problem Description Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500*xi+2*yi) dollars.
The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.
The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.
Input The input contains several test cases.
The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).
The following N lines each contains two integers xi(0 The following M lines each contains two integers xi(0 Output For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.
Sample Input

   1 2
100 3
100 2
100 1

Sample Output

   1 50004

对两者时间进行升序排序，遍历任务机器，把等级大于等于任务机器，时间大于等于任务机器的机器用数组储存，数组下标为机器等级，最后利用时间最少并且等级最低的机器来完成任务。数据要用到 long  long
详细题解： 点击打开链接

B  poj  1328

题目链接： 点击打开链接
Radar Installation

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 86974		Accepted: 19482

Description

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d. 

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates. 
 
Figure A Sample Input of Radar Installations

Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases. 

The input is terminated by a line containing pair of zeros 

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

Sample Input

3 2
1 2
-3 1
2 11 2
0 20 0

Sample Output

Case 1: 2
Case 2: 1

先用x坐标，对输入的每一个点，利用雷达半径作为圆的半径，以坐标点为圆心，找到两个与x轴的交点，按照左边的交点排序，若是交点超出相同范围，则雷达数++。 题目详解： 点击打开链接

C codeforce  651A

题目链接： 点击打开链接
A. Joysticks time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Friends are going to play console. They have two joysticks and only one charger for them. Initially first joystick is charged at a1 percent and second one is charged at a2 percent. You can connect charger to a joystick only at the beginning of each minute. In one minute joystick either discharges by 2 percent (if not connected to a charger) or charges by 1 percent (if connected to a charger).

Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joystick is charged by 1 percent, it has to be connected to a charger, otherwise the game stops. If some joystick completely discharges (its charge turns to 0), the game also stops.

Determine the maximum number of minutes that game can last. It is prohibited to pause the game, i. e. at each moment both joysticks should be enabled. It is allowed for joystick to be charged by more than 100 percent.

Input

The first line of the input contains two positive integers a1 and a2 (1 ≤ a1, a2 ≤ 100), the initial charge level of first and second joystick respectively.

Output

Output the only integer, the maximum number of minutes that the game can last. Game continues until some joystick is discharged.

Examples input 3 5 output 6 input 4 4 output 5 Note In the first sample game lasts for 6 minute by using the following algorithm:

at the beginning of the first minute connect first joystick to the charger, by the end of this minute first joystick is at 4%, second is at 3%;

continue the game without changing charger, by the end of the second minute the first joystick is at 5%, second is at 1%;

at the beginning of the third minute connect second joystick to the charger, after this minute the first joystick is at 3%, the second one is at 2%;

continue the game without changing charger, by the end of the fourth minute first joystick is at 1%, second one is at 3%;

at the beginning of the fifth minute connect first joystick to the charger, after this minute the first joystick is at 2%, the second one is at 1%;

at the beginning of the sixth minute connect second joystick to the charger, after this minute the first joystick is at 0%, the second one is at 2%.

After that the first joystick is completely discharged and the game is stopped.

水题不解释。

D   HDU  4296

题目链接： 点击打开链接

Buildings

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4218    Accepted Submission(s): 1566


Problem Description Have you ever heard the story of Blue.Mary, the great civil engineer? Unlike Mr. Wolowitz, Dr. Blue.Mary has accomplished many great projects, one of which is the Guanghua Building.
　　The public opinion is that Guanghua Building is nothing more than one of hundreds of modern skyscrapers recently built in Shanghai, and sadly, they are all wrong. Blue.Mary the great civil engineer had try a completely new evolutionary building method in project of Guanghua Building. That is, to build all the floors at first, then stack them up forming a complete building.
　　Believe it or not, he did it (in secret manner). Now you are face the same problem Blue.Mary once stuck in: Place floors in a good way.
　　Each floor has its own weight w _i and strength s _i. When floors are stacked up, each floor has PDV(Potential Damage Value) equal to (Σw _j)-s _i, where (Σw _j) stands for sum of weight of all floors above.
　　Blue.Mary, the great civil engineer, would like to minimize PDV of the whole building, denoted as the largest PDV of all floors.
　　Now, it’s up to you to calculate this value.

Input There’re several test cases.
　　In each test case, in the first line is a single integer N (1 <= N <= 10 ⁵) denoting the number of building’s floors. The following N lines specify the floors. Each of them contains two integers w _i and s _i (0 <= w _i, s _i <= 100000) separated by single spaces.
　　Please process until EOF (End Of File).

Output For each test case, your program should output a single integer in a single line - the minimal PDV of the whole building.
　　If no floor would be damaged in a optimal configuration (that is, minimal PDV is non-positive) you should output 0.

Sample Input

     3
10 6
2 3
5 4
2
2 2
2 2
3
10 3
2 5
3 3

Sample Output

     1
0
2

关键在于怎么排序，在试过几次之后，终于知道了要用重量和承受能力的和来排序。原因看详解。 题目详解： 点击打开链接

E  51nod  1125

题目链接： 点击打开链接
1125 交换机器的最小代价 基准时间限制：1 秒 空间限制：131072 KB 分值: 80  难度：5级算法题 有N台机器重量各不相等，现在要求把这些机器按照重量排序，重量从左到右依次递增。移动机器只能做交换操作，但交换机器要花费一定的费用，费用的大小就是交换机器重量的和。例如：3 2 1，交换1 3后为递增排序，总的交换代价为4。给出N台机器的重量，求将所有机器变为有序的最小代价。（机器的重量均为正整数） Input

第1行：1个数N，表示机器及房间的数量。（2 <= N <= 50000)
第2 - N + 1行：每行1个数，表示机器的重量Wi。(1 <= Wi <= 10^9)

Output

输出最小代价。

Input示例

3
3
2
1

Output示例

4

建议直接看详解，这个题谈论一晚上……………… 题目详解： 点击打开链接

F  poj   2586

题目链接： 点击打开链接
Y2K Accounting Bug

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 15252		Accepted: 7637

Description

Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc. 
All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite. 

Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post.

Input

Input is a sequence of lines, each containing two positive integers s and d.

Output

For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible.

Sample Input

59 237
375 743
200000 849694
2500000 8000000

Sample Output

116
28
300612
Deficit

每次上报都有亏损，说明连续5个月必有亏损，可以是1次，2次，3，4，5次，if—else if  判断即可 详细题解： 点击打开链接

G   poj  2109  

题目链接： 点击打开链接
Power of Cryptography

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 25239		Accepted: 12652

Description

Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers among these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be only of theoretical interest. 
This problem involves the efficient computation of integer roots of numbers. 
Given an integer n>=1 and an integer p>= 1 you have to write a program that determines the n th positive root of p. In this problem, given such integers n and p, p will always be of the form k to the n ^th. power, for an integer k (this integer is what your program must find).

Input

The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs 1<=n<= 200, 1<=p<10 ¹⁰¹ and there exists an integer k, 1<=k<=10 ⁹ such that k ⁿ = p.

Output

For each integer pair n and p the value k should be printed, i.e., the number k such that k n =p.

Sample Input

2 16
3 27
7 4357186184021382204544

Sample Output

4
3
1234

太可怕的输入，但是水过了，double还能这样用。
详细题解：点击打开链接

H  51nod  1115

环形最大M子段和，N个整数组成的序列排成一个环，a 1 1,a 2 2,a 3 3,…,a n n（a n−1 n−1, a n n, a 1 1也可以算作1段），将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。 例如：-2 11 -4 13 -5 6 -1，分为2段，6 -1 -2 11一段，13一段，和为27。

Input

第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 100000) 
第2 - N+1行：N个整数 (-10^9 <= a i i <= 10^9)

Output

输出这个最大和

Sample Input

7 2
-2
11
-4
13
-5
6
-2

Sample Output

26

不会做。。。。。。

I  codeforce  Good Bye 2014 c

题目链接： 点击打开链接
C. New Year Book Reading time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

New Year is coming, and Jaehyun decided to read many books during 2015, unlike this year. He has n books numbered by integers from 1 to n. The weight of the i-th (1 ≤ i ≤ n) book is wi.

As Jaehyun's house is not large enough to have a bookshelf, he keeps the n books by stacking them vertically. When he wants to read a certain book x, he follows the steps described below.

1. He lifts all the books above book x.
2. He pushes book x out of the stack.
3. He puts down the lifted books without changing their order.
4. After reading book x, he puts book x on the top of the stack.

He decided to read books for m days. In the j-th (1 ≤ j ≤ m) day, he will read the book that is numbered with integer bj (1 ≤ bj ≤ n). To read the book, he has to use the process described in the paragraph above. It is possible that he decides to re-read the same book several times.

After making this plan, he realized that the total weight of books he should lift during m days would be too heavy. So, he decided to change the order of the stacked books before the New Year comes, and minimize the total weight. You may assume that books can be stacked in any possible order. Note that book that he is going to read on certain step isn't considered as lifted on that step. Can you help him?

Input

The first line contains two space-separated integers n (2 ≤ n ≤ 500) and m (1 ≤ m ≤ 1000) — the number of books, and the number of days for which Jaehyun would read books.

The second line contains n space-separated integers w1, w2, ..., wn (1 ≤ wi ≤ 100) — the weight of each book.

The third line contains m space separated integers b1, b2, ..., bm (1 ≤ bj ≤ n) — the order of books that he would read. Note that he can read the same book more than once.

Output

Print the minimum total weight of books he should lift, which can be achieved by rearranging the order of stacked books.

Examples input

3 5
1 2 3
1 3 2 3 1

output

12

Note

Here's a picture depicting the example. Each vertical column presents the stacked books.

题目中给出的顺序即可当作初始顺序，然后就是暴力就解决了。 题目详解： 点击打开链接

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！