Untitled

Một cửa hàng cần hiển thị quảng cáo 3 lần một ngày.

Tuy nhiên, họ chỉ có 1 bảng điện để hiển thị quảng cáo, do đó họ nên chọn thời gian hiển thị quảng cáo để du khách có thể xem chúng nhiều nhất có thể.

 

Khi khách truy cập xem quảng cáo, họ có thể nhận được điểm được tính như sau:

1. Ba quảng cáo có độ dài L1, L2, L3 và số điểm mà một người có thể nhận được sau khi xem chúng P1, P2, P3.

2. Khách truy cập chỉ có thể nhận được điểm của Quảng cáo khi họ xem Quảng cáo đầy đủ (từ đầu đến cuối Quảng cáo đó)

3. Khi khách truy cập xem nhiều Quảng cáo và cũng nhận được điểm cho họ, chỉ Quảng cáo có điểm cao nhất mới được trao cho người đó.

4. Chỉ có một Quảng cáo có thể được hiển thị trên bảng điện tại một thời điểm (Nhưng Quảng cáo tiếp theo có thể được hiển thị ngay sau khi Quảng cáo trước đó kết thúc)

 

Với độ dài của mỗi Quảng cáo L1, L2, L3 và điểm đạt được cho họ P1, P2, P3, thời gian đến của mỗi khách truy cập vào cửa hàng và khoảng thời gian họ ở lại cửa hàng, hãy viết một chương trình để chọn thời gian hiển thị quảng cáo để có thể trao càng nhiều điểm càng tốt cho khách truy cập. In ra tổng số điểm mà khách truy cập có thể nhận được.

[Ràng buộc]

- Số lượng khách truy cập N (1 ≤ N ≤ 50)

- Thời gian đến Ai, khoảng thời gian Di của mỗi khách truy cập và độ dài của mỗi Quảng cáo L1, L2, L3 được cho là số nguyên (1 ≤ Ai, Di, L1, L2, L3 ≤ 50)

- Ai + Di ≤ 50

- L1 + L2 + L3 ≤ 50

- Thời gian bắt đầu của Quảng cáo: 1 ≤ thời gian bắt đầu ≤ 50

- P1, P2, P4 là các số nguyên (1 ≤ P1, P2, P3 ≤ 1000)

 

[Nhập]

Dòng thứ 1 cho T - tổng số TC (T ≤ 50)

Trong mỗi TC :

- Dòng thứ 1 chứa N, L1, L2, L3, P1, P2, P3 theo thứ tự này

- Các dòng N tiếp theo: mỗi dòng cho biết thời gian đến và khoảng thời gian Di của mỗi khách truy cập

5 // Số trường hợp kiểm thử T = 5

7 1 2 3 1 2 3 // Trường hợp thử nghiệm 1 N = 7, L1 = 1, L2 = 2, L3 = 3, P1 = 1, P2 = 2, P3 = 3

2 2                       // A1 = 2, D1 = 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

Trường hợp #1

12

Trường hợp #2

18