## DMOPC '19 Contest 6 P5 - University Math

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

It's Jack's first day of freshman year at the University of Fireloo! He looks at his timetable but is disappointed to find that he has to take data management again. Having grown tired of drawing charts, he decides to challenge himself to draw as efficiently as he can!

Today, Jack is trying to draw a histogram! A histogram consists of bars of positive height, with widths respectively. He considers a drawing of a histogram to be complete if the four sides of each rectangular bar have been traced over at least once and there are no extraneous marks on the sheet. He realizes that since all bars are adjacent, he can make his drawing complete without removing his pencil from the drawing once he chooses where to start drawing. And in order to assess his efficiency, he wishes to find the optimal way to draw that minimizes the total distance travelled by his pencil tip during the entire process.

Having experimented with this challenge for a few hours now, he has analyzed scenarios, where in the -th scenario, he draws all bars from to inclusive. Help him determine the minimal distance his pencil needs to travel in each scenario!

#### Constraints

All are equal. That is, .

#### Input Specification

The first line contains two space-separated integers, .
The second line contains space-separated integers, .
The third line contains space-separated integers, .
The next lines contains two space-separated integers, .

#### Output Specification

Output integers on separate lines. The -th integer should be the answer to the -th query.

#### Sample Input 1

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

#### Sample Output 1

34
32
50
16
27
18

#### Explanation for Sample Output 1

In the diagram of Sample Input 1, the numbers at the bottom indicate the width of each bar while the numbers inside each bar indicate the height of the bar. Suppose we apply a coordinate system to this diagram with the bottom-left corner of the first bar being at .
For the first query, one optimal way to draw would be:

• Start drawing at
• Move unit left to
• Move units down to
• Move units right to
• Move units up to
• Move unit left to
• Move units down to
• Move units left to
• Move units up to
• Move units right to

The total distance moved is units. The boundaries of the first three bars have been drawn over at least once and it is impossible to do so using a shorter distance.

#### Sample Input 2

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

#### Sample Output 2

58
23
41
119
103
22
52

#### Sample Input 3

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

#### Sample Output 3

44
64
24
28
54