## Description

Your teacher is demonstrating his studentsβ Martial Arts capabilities by breaking boards at the

local mall. He wants the demonstration to be interesting, but he has a limited number of boards.

Each board can be represented as a rectangle with an integral width and height. When broken it

requires some amount of effort, and will become two new boards. The board will always break

along the length of the board. Each break will be a straight line parallel to one side of the board.

The break will occur at an integral distance from the parallel side and as close to the center as

possible.

As an example, a board of length 7 and height 2 will break into two, one of length 4 and height 2

and the other of length 3 and height 2. Additionally a board of length 4 and height 18, will break

into two boards for length 2 and height 18.

Your teacher will initially have each board he has brought held by an audience member. Each

audience member will form their own line. When a board is broken the board holder and the

student that the broke the board each pick up a part and go back into line the board came from.

Only the board at the front of their respective line can be broken.

The teacher wants the audience members to get a lot of action, so instead of going to the back

of the line these new board holders will go to the front, where the original board holder will be

the first in line and the board breaker will be second. The resulting front most board holder will

always have the board piece that has the largest surface area (i.e. πΏ Γ π» is maximized). If a

board is ever non-breakable (i.e. 1 Γ π»), then the board holder will leave the line and watch the

demonstration from the sidelines.

Each student is different and has a limit to the amount of effort they can expend when breaking a

board. These students will also line up.

When given the signal the first student in line tries to break a board. When a student tries to

break a board they go to the line where the first board in the line has the highest effort board,

which the student can break. If no such line exists, the student goes to the end of the student line.

If multiple line options have the same effort the student will go into the first one by index.

If no student in line can break a board, the demonstration ends. Additionally, if no boards are left

to break, the demonstration ends.

The effort (πΈ) it takes to break a board with length, πΏ, and height, π», is the following,

πΈ(πΏ, π») = max(1, 2 Γ π» β πΏ)

Your teacher wants to know both the sum of the effort the students will expend, the total number

of boards left, and the number of students that do not break any boards. Your teacher will fiddle

with the order of students and the boards brought to make the demonstration as cool as possible,

so you should design your program such that it can handle a variety of test cases.

Input specification

Input will begin with 2 positive integers, π and π (π Γ π β€ 100,000), representing the number of

boards and the number of students respectively. The next π lines contains a single pair of spaceseparated, positive integers, π and π (2 β€ π, π β€ 100,000,000), representing the length and

height of the board brought by your teacher. The earlier the board occurs in input the smaller the

index of its line. The last line contains π space-separated, positive integers, ππ, ππ, β¦ , ππ

, where

ππ

(ππ β€ 100,000,000) represents the maximum board breaking effort for the π-th student in

line.

Output Specification

Output should contain 3 integers on their own line, πΈ, π΅, and π, representing the sum of the

effort, the number of remaining boards, and the number of students that did not break a board

respectively.

Input Output Example

Input Output

3 7

10 5

3 9

5 5

8 6 10 10 3 2 10

29

3

2

2 3

5 5

3 5

5 8 7

19

3

0

1 1

2 2

1

0

1

1

Explanation

Case 1

The effort for the first three boards are the following

ο· The effort to break 10 by 5 is either (2 x 5 β 10) = 0 or 1. Therefore, 1 is the effort to

break the 10 by 5 board.

ο· The effort to break 3 by 9 is either (2 x 9 β 3) = 15 or 1. Therefore, 15 is the effort to

break the 3 by 9 board.

ο· The effort to break 5 by 5 is either (2 x 5 β 5) = 5 or 1. Therefore, 5 is the effort to break

the 5 by 5 board.

1

st Student (skill of 8)

The initial board set up looks like the following

110×5

1 23×9

55×5

The 5 board is broken by the student, because it is the highest effort board they can break

110×5

1 23×9 82×5 73×5

When broken we get two boards a 2 by 5 and a 3 by 5. The efforts are 2 x 5 β 2 and 2 x 5 β 3.

The 2 by 5 will be behind the 3 by 5 board which will be the start of the line for the given

example.

110×5

1 23×9

73×5

82×5

2

nd Student (skill of 6)

The second student will break the 10 by 5 board in the first line.

55×5

1 23×9

73×5

82×5 55×5

Since the boards are the same the order does not really matter

55×5

1 23×9

73×5

55×5 82×5

3

rd Student (skill of 10)

The third student will break the 7 effort 3 by 5 board at the front of the third line

55×5

1 23×9

55×5 82×5 82×5

Part of the broken board will be tossed since itβs length be comes 1. The remaining piece can be

reused and will go on the top of the stack.

55×5

1 23×9

55×5 82×5

82×5

4

th Student (skill of 10)

The fourth student will break the 8 effort 2 by 5 board at the front of the third line. Both pieces

are unusable and will be tossed.

55×5

1 23×9

55×5 82×5

Resulting in the following

55×5

1 23×9

55×5 82×5

The 5th and 6th student (skill of 3 and 2)

The next two students cannot break anything. They will go to the end of the line hoping that the

7

th student will allow for easier boards.

The 8th student (skill of 10)

The 8th student will break the hardest board he can, the 8 effort 2 by 5 board in the third line.

This board when broken will have both pieces discarded.

55×5

1 23×9

55×5

Resulting in the following board setup,

55×5

1 23×9

55×5

The remaining students cannot break any boards, so the demonstration ends.

The total effort was 5 + 1 + 7 + 8 + 8, which totals to 29. There was 3 boards left and 2 students

that did not break anything.

Case 2

There are only two boards the first board is a 5 by 5 which has an effort of 5 to break. The

second board is a 3 by 5 which has an effort of 7 to break.

The first student has a skill of 5 so he can break the first board. This break creates two usable

boards. The board that will be at the front of the line will be a 3 by 5 and has an effort of 7 to

break. The other board behind this first one will be a 2 by 5 and has an effort of 8 to break.

The next student has a skill of 8 and can break either board, both have an effort of 7. They

choose the board with the lowest line index (the first line). After breaking this board there are

now two 2 by 5 board with effort 8 in the first line and one board with effort 7 in the second line.

The other board had a length of 1 and was subsequently tossed.

The last student has a skill of 7, which allows them to break the board in line 2. This break

creates another 2 by 5 board with effort 8 in the second line. Another board with length of 1 is

tossed.

All three students have gone, so the demonstration ends. The students expended 5 + 7 + 7 = 19

effort, which is one less than the maximum they could have achieved given these boards. There

are 3 boards and 0 students left in this demonstration.

Case 3

The only board has an effort of 2 x 2 β 2 = 2, but the only student cannot break any boards harder

than 1, so no boards are broken. We have 0 effort, 1 board and 1 student left.

Grading Information

Read/write in from standard input/output β 5 points

Comments, variable names, whitespace usage β 15 points

Use an array (or some listing) of stack to represent the board lines β 10 points

Use a queue to represent the student lineβ 10 points

Use some simulation to determine the ultimate outcomes β 10 points

Your program will be tested on 25 test cases β 2 points each

No points will be awarded to programs that do not compile.

Solutions without linked lists based stacks/queues will receive a maximum of 50 points