Untitled

Hugo Xếp Lịch Quảng Cáo
Hugo’s shop need to display the advertisement 3 times a day.

However, they only has 1 electric board to display the advertisement, hence they should select the time to display advertisements so that visitors can watch them as much as possible.

 

When visitors watch advertisement, they can get points which calculated as below :

1. Three Ads  have length L1, L2, L3 and the points a person can get after watched them P1, P2, P3.

2. A visitor can get the point of a Ads  only when he/she watch the Ads  fully (from beginning to the end of that Ads )

3. When a visitor watch more than one Ads  and also get the point for them, only the Ads  with highest point will be given to that person.

4. Only one Ads  can be displayed on electric board at a time (But the next Ads  can be displayed right after the previous one ended)

 

Given the length of each Ads L1, L2, L3 and the point gained for them P1, P2, P3, the arrival time of each visitor into the shop and the time duration that he/she stay in the shop, write a program to select advertisement display time so that as many points as possible can be given to visitors. Print out the total sum of points that the visitors can get.


[Constraints]

- The number of visitors N (1 ≤ N ≤ 50)

- The arrival time Ai, the time duration Di of each visitor and the length of each Ads L1, L2, L3 are given as integers (1 ≤ Ai, Di, L1, L2, L3 ≤ 50)

- Ai + Di ≤ 50

- L1 + L2 + L3 ≤ 50

- The starting time of an Ads : 1 ≤ starting time ≤ 50

- P1, P2, P4 are integers (1 ≤ P1, P2, P3 ≤ 1000)

 

[Input]

The 1st line given T - the total number of TC (T ≤ 50)

In each TC :

 - The 1st line contains N, L1, L2, L3, P1, P2, P3 in this order

 - The next N lines : each line gives the arrival time Ai and time duration Di of each visitor


input:
50
7 1 2 3 1 2 3
2 2
6 4
3 3
7 2
1 1
2 1
1 10
4 3 2 1 6 4 3
1 5
1 3
2 4
2 2
3 1 2 3 7 6 4
10 1
11 2
13 3
5 2 2 1 2 5 4
2 4
4 6
9 1
14 10
30 15
50 31 4 1 734 134 546 
1 39
4 28
9 24
12 16
7 29
6 27
12 14
24 18
1 34
11 20
5 23
31 16
12 38
3 35
10 2
35 14
11 34
31 13
6 14
10 7
4 17
15 19
7 36
8 19
13 20
7 18
27 6
9 5
13 14
2 20
9 12
5 13
34 12
5 20
17 7
18 31
33 6
14 8
4 6
10 38
23 10
36 13
17 15
27 20
11 21
27 1
31 13
20 16
47 2
19 26
6 3 4 3 12 9 10
1 3
4 4
8 4
7 4
8 3
1 4
6 1 3 1 11 3 11
17 24
28 7
20 30
4 46
16 6
1 47
6 1 5 2 34 30 17
20 10
1 22
13 2
27 8
8 41
16 33
3 2 3 2 38 43 5
19 4
8 33
11 36
1 2 3 1 19 43 38
11 11
14 2 2 1 70 71 44
11 23
8 26
10 36
17 31
30 12
27 8
33 10
3 32
28 2
8 12
22 26
4 21
15 15
1 13
7 6 9 6 23 74 26
1 15
34 12
26 24
25 12
43 6
12 34
2 18
18 4 4 1 26 68 46
33 6
8 16
45 2
42 1
9 23
43 6
11 20
34 1
23 2
14 2
23 19
21 10
8 6
43 7
21 29
6 2
17 1
30 12
20 5 3 6 14 24 41
5 36
31 12
2 35
4 15
44 1
2 9
5 39
19 2
28 5
25 21
3 28
7 18
1 31
17 9
7 4
4 30
36 7
17 24
1 20
16 3
11 2 3 9 89 39 11
30 2
8 41
13 9
20 9
18 9
23 20
26 11
14 33
8 35
12 35
9 26
7 3 4 10 47 79 87
2 24
1 41
8 1
9 5
24 2
30 1
7 29
7 7 8 8 56 80 39
7 26
35 5
16 28
14 29
16 32
21 18
3 26
12 8 2 9 17 72 28
8 29
4 1
17 24
40 2
21 8
6 9
5 13
17 9
5 39
4 31
28 4
3 36
7 1 8 5 98 57 61
1 4
30 1
27 13
7 11
10 16
21 14
33 9
6 10 5 2 62 3 32
5 21
15 31
10 29
11 15
26 8
5 15
14 12 5 16 145 173 246
29 6
19 28
18 31
33 12
14 30
29 19
33 11
11 16
14 33
6 38
44 5
16 20
18 22
4 38
23 20 6 20 480 471 199
24 23
10 9
9 29
39 6
19 27
24 8
23 12
15 18
23 19
27 8
27 16
14 11
46 3
13 36
4 39
18 19
40 10
16 8
20 28
5 19
26 7
27 13
12 36
21 11 8 12 167 294 326
31 7
19 11
47 3
2 1
4 17
16 12
13 30
14 17
3 44
10 22
24 4
35 8
26 22
19 7
6 30
23 7
32 12
36 8
13 21
24 1
33 7
23 8 3 4 204 177 128
22 14
18 10
7 24
8 21
4 25
14 31
9 34
10 36
6 6
24 18
19 3
39 10
32 3
23 20
20 10
21 20
16 30
20 26
22 17
24 10
14 13
2 10
39 10
15 8 19 11 94 352 337
33 6
8 37
26 3
5 7
29 15
23 2
15 20
26 14
12 23
6 6
25 3
35 13
36 4
15 27
21 1
12 2 16 11 102 320 452
35 14
7 32
3 19
21 26
11 21
24 2
15 10
32 6
38 7
4 31
6 8
10 33
13 2 15 6 194 80 243
13 14
16 2
18 22
13 13
43 6
4 35
30 19
12 17
5 11
7 7
28 18
11 30
4 25
19 5 6 14 138 401 439
45 3
5 5
29 19
23 13
2 7
13 7
11 10
19 1
3 15
37 8
6 11
16 11
19 6
11 32
4 44
10 12
17 13
19 12
6 29
14 2 6 17 201 14 43
18 11
28 13
14 15
12 4
16 9
12 22
4 29
4 15
1 38
24 16
26 17
19 9
31 9
5 21
14 6 11 20 115 187 321
23 24
3 27
12 9
28 18
35 12
6 5
7 5
16 32
1 5
21 11
11 38
36 3
11 23
26 17
29 22 25 1 881 884 274
21 20
23 12
12 16
4 8
6 28
29 8
24 4
1 45
30 12
20 18
29 21
12 36
12 9
15 5
14 15
2 1
30 11
4 27
2 4
31 16
9 17
10 17
45 3
17 14
29 13
17 16
37 2
39 6
30 12
23 13 23 12 498 643 634
8 2
24 1
14 23
2 46
4 46
3 43
7 4
2 13
46 4
2 26
10 20
21 27
9 25
1 25
22 15
10 4
10 25
11 16
5 41
13 12
32 3
35 14
8 31
22 8 21 11 467 961 900
6 23
21 6
36 3
29 6
11 30
17 28
36 14
40 4
24 21
7 37
1 46
2 44
17 12
28 3
34 3
14 18
28 19
11 28
29 10
9 11
1 11
38 4
26 7 20 19 787 304 842
12 7
3 34
27 3
2 48
21 26
7 11
23 22
11 38
24 5
1 41
14 1
4 24
15 21
31 17
5 25
32 12
2 24
12 26
39 5
13 12
36 8
11 9
10 1
6 12
25 11
19 16
34 11 20 16 459 207 689
22 7
23 24
4 34
14 23
23 26
5 21
1 34
13 20
24 11
3 4
10 18
7 28
5 27
16 29
1 24
33 5
16 29
20 11
14 35
11 37
8 3
7 14
41 5
23 3
15 25
29 8
32 3
5 30
6 17
12 31
5 29
44 5
29 20
14 4
31 12 13 22 237 822 823
33 16
25 3
9 34
13 34
25 16
1 45
14 17
15 25
46 4
16 17
10 8
20 4
31 6
33 17
1 31
30 12
7 7
10 5
24 6
13 28
5 3
15 25
2 34
18 9
39 11
7 41
2 46
7 36
23 6
6 36
7 35
33 2 8 25 625 390 641
20 2
18 20
7 1
36 1
30 15
31 13
9 11
43 1
19 24
13 35
8 37
16 9
21 8
19 10
19 14
30 2
6 10
3 19
3 38
30 4
12 21
12 36
22 27
1 2
22 6
41 6
3 20
3 2
16 32
37 3
23 7
4 33
9 15
25 20 4 7 119 439 977
26 1
7 4
21 27
3 16
5 14
15 26
34 10
3 29
15 24
5 13
3 28
33 17
30 13
20 10
20 13
16 28
14 7
1 4
41 3
4 23
30 6
16 30
10 30
19 27
5 39
22 7 2 23 435 733 788
37 2
25 7
15 28
31 5
24 1
32 4
36 5
35 12
31 9
1 23
17 18
32 10
30 14
22 2
1 9
19 23
21 2
31 17
17 31
8 30
41 5
18 27
22 7 12 9 393 913 905
1 16
37 9
21 20
15 13
18 21
5 38
11 14
27 13
14 35
26 17
8 28
19 10
24 12
9 40
5 10
21 1
11 34
19 15
10 30
22 19
24 23
1 23
33 8 32 7 942 106 497
49 1
15 4
6 28
22 19
27 6
10 40
33 5
23 11
20 18
28 15
21 4
5 6
9 15
39 7
21 16
5 34
3 21
28 5
36 1
22 18
17 6
6 16
26 2
39 3
8 19
9 30
12 24
3 9
19 19
36 12
10 1
19 7
28 21
48 1 4 36 965 152 460
27 11
4 26
2 45
23 15
5 26
11 26
2 9
12 29
7 19
13 21
20 8
28 12
12 31
40 2
19 11
18 14
34 8
20 9
32 2
17 33
28 3
36 9
14 35
4 19
3 27
8 7
11 33
10 14
18 22
11 21
11 5
6 36
10 25
26 6
24 24
35 8
15 9
29 12
17 1
11 13
1 6
7 20
16 22
31 8
17 19
34 12
15 25
3 3
43 13 22 9 688 476 169
16 21
11 13
44 5
21 12
26 7
16 24
6 30
36 2
14 32
2 48
9 20
27 5
30 9
11 27
26 13
33 12
7 28
26 19
16 30
3 7
5 17
21 4
2 28
25 21
2 2
11 4
2 48
26 21
9 30
12 2
9 30
4 23
10 19
13 32
26 23
24 14
15 5
4 28
17 11
31 4
4 13
5 17
10 10
37 14 4 15 463 441 250
10 14
36 12
18 28
3 27
7 36
16 16
11 12
24 22
36 6
31 5
9 40
6 10
28 11
43 1
40 5
11 27
25 8
29 3
14 31
2 4
12 23
24 24
33 10
19 11
38 10
32 11
24 10
16 30
42 5
22 16
20 16
3 3
1 5
30 8
8 39
10 22
1 26
31 17 4 4 979 652 689
32 17
26 13
34 16
8 34
24 21
4 12
6 26
4 26
28 8
26 19
7 41
36 8
26 11
32 15
8 9
9 14
37 9
36 5
32 3
27 14
27 3
2 48
8 28
7 25
28 11
26 6
39 9
23 8
39 6
5 40
27 8
50 16 23 2 947 875 329
1 41
35 6
3 28
12 15
28 20
22 21
23 22
35 2
23 15
32 12
10 31
18 8
1 25
22 1
44 6
26 17
18 17
14 21
16 2
17 6
26 20
17 21
45 3
11 31
31 9
21 10
6 23
48 2
10 36
14 29
1 11
34 15
44 3
17 16
9 15
28 17
35 11
7 4
17 30
2 18
38 8
21 24
1 13
4 28
18 24
17 21
25 14
7 3
48 2
36 9
50 22 8 8 756 883 690
16 11
8 30
45 3
42 6
26 22
7 39
4 27
19 7
14 20
48 2
15 8
9 1
3 15
16 4
1 6
39 10
15 28
27 2
34 11
26 14
33 14
2 7
15 27
5 27
19 8
17 5
11 24
2 44
9 41
7 39
8 14
3 3
34 11
16 32
35 14
12 13
12 19
7 20
36 12
15 27
3 22
1 22
19 4
5 14
37 8
43 1
9 31
2 21
12 29
16 7
50 21 18 2 471 299 613
8 10
19 20
20 11
39 11
46 4
30 17
13 27
19 6
16 24
29 1
25 14
37 8
25 3
22 27
18 22
15 10
10 7
25 12
36 11
14 4
27 22
7 27
33 3
8 24
5 27
24 14
33 4
7 41
16 26
37 9
26 8
18 15
14 36
21 4
34 4
5 44
19 20
18 23
10 40
12 14
10 15
42 3
25 21
31 11
18 14
12 9
2 3
17 10
10 1
26 4
50 9 2 19 627 406 191
7 33
14 32
13 19
2 28
2 8
16 34
6 12
5 16
6 4
43 7
2 35
6 16
28 10
40 7
39 6
1 43
27 7
18 23
12 33
23 4
16 30
29 11
7 35
18 1
14 5
42 2
18 25
13 27
31 11
19 1
2 2
31 14
1 36
23 15
9 34
10 35
48 2
7 18
12 27
22 22
20 15
7 2
13 1
10 3
4 45
15 24
1 36
17 5
14 23
39 5
50 2 6 6 223 60 491
39 3
27 12
21 2
39 5
2 1
12 2
35 9
15 12
6 33
6 18
2 16
9 40
15 15
6 23
8 1
16 6
29 18
14 12
10 11
2 41
3 13
6 11
12 11
15 6
22 21
44 5
14 17
14 15
1 11
6 25
6 43
17 7
12 27
5 40
18 19
15 30
22 5
4 34
1 14
19 30
23 5
4 31
28 13
28 4
5 30
6 23
27 20
5 10
2 33
10 29

output:

Case #1
12
Case #2
18
Case #3
17
Case #4
16
Case #5
17998
Case #6
65
Case #7
66
Case #8
183
Case #9
129
Case #10
43
Case #11
937
Case #12
297
Case #13
554
Case #14
507
Case #15
801
Case #16
340
Case #17
480
Case #18
560
Case #19
473
Case #20
283
Case #21
2487
Case #22
7074
Case #23
3331
Case #24
3673
Case #25
1745
Case #26
2784
Case #27
2283
Case #28
3874
Case #29
1679
Case #30
1601
Case #31
5940
Case #32
8604
Case #33
9501
Case #34
10561
Case #35
11023
Case #36
12804
Case #37
11560
Case #38
13919
Case #39
10156
Case #40
14834
Case #41
12847
Case #42
28236
Case #43
12022
Case #44
8974
Case #45
18597
Case #46
15569
Case #47
24063
Case #48
15796
Case #49
17669
Case #50
13928