Problem Statement

Takahashi is going to participate in a cooking contest.

In this contest, there are N types of basic recipes prepared by the organizers, each of which has an integer value called a "base score." The base score of the i-th (1 \leq i \leq N) basic recipe is A_i.

Takahashi plans to make M dishes. For the j-th (1 \leq j \leq M) dish, he will use basic recipe B_j as the base. Note that different dishes may use the same basic recipe as their base.

The score of each dish is the base score of the underlying basic recipe plus the arrangement score S_j that Takahashi adds. That is, the score of the j-th dish is A_{B_j} + S_j. The arrangement score can be negative, in which case the dish's score will be lower than the base score. It is also possible for the dish's score itself to be negative.

In the contest, Takahashi's ranking is determined by the total score of the M dishes he makes.

Find the total score of Takahashi's dishes. Note that the total score may be negative.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_j \leq N (1 \leq j \leq M)
• -10^9 \leq S_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers

Sample Input 1

3 2
10 20 30
1 5
3 -10

Sample Output 1

35

Sample Input 2

5 4
100 200 300 400 500
2 50
4 -100
1 200
5 0

Sample Output 2

1350

Sample Input 3

10 8
1000000000 500000000 300000000 700000000 100000000 900000000 200000000 800000000 600000000 400000000
1 -500000000
6 1000000000
3 -300000000
10 999999999
5 100000000
8 -800000000
2 500000000
7 0

Sample Output 3

5199999999

Problem Statement

Takahashi's company has N devices, each of which consumes electric power.

The current power consumption of the i-th device (1 \leq i \leq N) is A_i watts. Takahashi must select exactly K devices from these N devices and set them to "energy-saving mode".

The power consumption of a device set to energy-saving mode becomes the original power consumption halved, with the fractional part discarded. That is, if a device with power consumption A_i watts is set to energy-saving mode, its power consumption becomes \lfloor A_i / 2 \rfloor watts. Here, \lfloor x \rfloor denotes the largest integer not exceeding x. The power consumption of devices not set to energy-saving mode remains A_i watts.

Each device is either set to energy-saving mode or not, and the same device cannot be selected more than once.

Takahashi wants to minimize the total power consumption of all devices by choosing the K devices to set to energy-saving mode wisely.

Find the minimum total power consumption.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

5 2
10 7 3 8 5

Sample Output 1

24

Sample Input 2

4 4
100 50 30 20

Sample Output 2

100

Sample Input 3

8 3
1000000000 999999999 500000000 123456789 987654321 111111111 222222222 333333333

Sample Output 3

2783950614

Problem Statement

Takahashi works part-time at a library. The library has a bookshelf with N books arranged in a row, and Takahashi has been assigned to organize this bookshelf.

The books are numbered from 1 to N from left to right, and organizing book i (1 \leq i \leq N) takes A_i minutes. Since Takahashi only has K minutes available for today's shift, he may not be able to organize the entire bookshelf.

Therefore, Takahashi has decided to choose one contiguous interval from the bookshelf and organize all the books within that interval. Specifically, he chooses integers l, r (1 \leq l \leq r \leq N) and organizes all books from book l to book r. The total time required for organizing is A_l + A_{l+1} + \cdots + A_r minutes.

Takahashi wants to choose an interval such that the total organizing time is at most K minutes. Among all intervals satisfying this condition, maximize the number of books organized, r - l + 1.

In other words, find the maximum value of r - l + 1 over all integer pairs (l, r) (1 \leq l \leq r \leq N) satisfying

A_l + A_{l+1} + \cdots + A_r \leq K

However, if no such (l, r) exists, that is, if A_i > K for all i (1 \leq i \leq N), output 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{15}
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

5 10
3 1 4 1 5

Sample Output 1

4

Sample Input 2

8 15
5 2 6 3 1 2 4 7

Sample Output 2

5

Sample Input 3

10 1000000000000
500000000 200000000 300000000 100000000 400000000 600000000 150000000 250000000 350000000 450000000

Sample Output 3

10

Problem Statement

Takahashi is in charge of caring for N flowers arranged in a row in his garden. The flowers are numbered 1, 2, \ldots, N from left to right, and the height of flower i is A_i.

Takahashi has decided to ask K friends to share the task of watering the flowers. The assignment follows these rules:

• Divide the N flowers into exactly K non-empty contiguous intervals while preserving their original order. That is, choose an integer sequence r_0, r_1, \ldots, r_K satisfying 0 = r_0 < r_1 < r_2 < \cdots < r_K = N, where the j-th friend (1 \leq j \leq K) is responsible for flowers from r_{j-1}+1 to r_j.
• The effort of each interval is defined as the difference between the maximum and minimum heights of the flowers contained in that interval. If an interval contains only one flower, the effort is 0.
• The sum of the efforts of the K intervals is called the total effort.

Takahashi wants to partition the flowers so that the total effort is as small as possible.

Find the minimum value of the total effort.

Constraints

• 1 \leq K \leq N \leq 200
• 1 \leq A_i \leq 1000
• All inputs are integers.

Sample Input 1

5 2
3 1 4 1 5

Sample Output 1

3

Sample Input 2

6 3
10 1 10 1 10 1

Sample Output 2

9

Sample Input 3

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

Sample Output 3

8

Sample Input 4

20 5
15 3 12 7 20 1 18 5 14 9 2 16 8 11 4 19 6 13 10 17

Sample Output 4

19

Sample Input 5

1 1
42

Sample Output 5

0

Problem Statement

Takahashi works as a delivery driver, delivering packages to customers every day.

The area Takahashi is responsible for consists of N intersections and M roads. The intersections are numbered from 1 to N. The i-th road (1 \leq i \leq M) bidirectionally connects intersection U_i and intersection V_i, and it takes W_i minutes to traverse in either direction. There may be multiple roads connecting the same pair of intersections.

Today there are K delivery requests. The j-th request (1 \leq j \leq K) requires delivering a package to a customer at intersection D_j. All K delivery destination intersections are distinct, and none of them is the same as intersection S where the office is located. Takahashi must depart from intersection S where the office is located, visit all K delivery destinations, and then return to intersection S. He is free to choose the order in which he visits the delivery destinations. He may pass through the same intersection or the same road any number of times during his travel.

A delivery to a destination is automatically completed the moment Takahashi passes through that intersection, even if it is in the middle of traveling to another destination. In other words, if he passes through a delivery destination while heading to a different one, the delivery to that destination is also completed. The time for handing over packages is negligible.

Find the minimum total travel time (in minutes) to complete all deliveries and return to the office.

It is guaranteed that all delivery destinations are reachable from intersection S (since the roads are bidirectional, it is also possible to return from each delivery destination to intersection S).

Constraints

• 2 \leq N \leq 10\,000
• 1 \leq M \leq 20\,000
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• 1 \leq W_i \leq 10^6
• 1 \leq S \leq N
• 1 \leq K \leq 15
• 1 \leq D_j \leq N
• All D_j are distinct
• D_j \neq S
• All delivery destinations are reachable from S
• All input values are integers

Sample Input 1

4 5
1 2 2
2 3 3
3 4 4
1 4 7
1 3 10
1 2
3 4

Sample Output 1

16

Sample Input 2

6 8
1 2 3
1 3 5
2 3 1
2 4 7
3 5 4
4 5 2
4 6 3
5 6 6
1 3
4 5 6

Sample Output 2

26

Sample Input 3

10 14
1 2 5
1 3 12
2 3 4
2 4 8
3 5 3
4 5 6
4 6 2
5 7 7
6 7 4
6 8 9
7 9 3
8 9 5
8 10 2
9 10 6
1 5
3 5 7 9 10

Sample Output 3

54