Lịch trình xe buýt

Bạn dự định di chuyển bằng xe buýt trong những ngày tới và đã có một lịch trình chi tiết về các ngày cần đi cũng như quãng đường của từng chuyến đi trong mỗi ngày cụ thể.

Công ty xe buýt phát hành 5 loại vé:

• Loại 1: Vé theo lượt, giá vé phụ thuộc vào quãng đường di chuyển của chuyến đi. Có 3 mức giá khác nhau: chặng ngắn có quãng đường $\leq 3$ km, chặng trung bình có quãng đường $> 3$ km và $\leq 10$ km, và chặng dài có quãng đường $> 10$ km.
• Loại 2: Vé ngày, hết hạn vào lúc 00:00 ngày hôm sau.
• Loại 3: Vé tuần, hết hạn vào lúc 00:00 ngày thứ Hai của tuần tiếp theo. Nếu bạn mua vé này vào thứ Sáu, bạn chỉ có thể sử dụng vé đến hết đêm Chủ nhật chứ không được đủ 7 ngày.
• Loại 4: Vé tháng, hết hạn vào lúc 00:00 ngày đầu tiên của tháng sau. Nếu bạn mua vé vào ngày 28 của tháng, vé cũng sẽ hết hạn vào cuối đêm của ngày cuối cùng trong tháng đó.
• Loại 5: Vé năm, hết hạn vào lúc 00:00 ngày đầu tiên của năm sau. Nếu bạn mua vé vào ngày 31/12, vé sẽ hết hạn vào lúc 00:00 ngày 01/01.

Hãy viết chương trình tính tổng chi phí mua vé nhỏ nhất để hoàn thành kế hoạch di chuyển trên.

Ràng buộc

• 01/01/2000 (Thứ Bảy) $\leq$ DD/MM/YYYY là một ngày tháng năm hợp lệ.
• $1 \leq N \leq 10^5$
• $1 \leq d_i \leq 10^5$
• $\sum_{i = 1}^n k_i \leq 10^5$
• $1 \leq$ quãng đường của mỗi chuyến đi $\leq 15$.
• $1 \leq$ giá vé của các loại $\leq 10^9$
• $d_1 < d_2 < d_3 < ... < d_n$

Subtask (tham khảo)

• $10/30$ testcase có $\sum_{i = 1}^n k_i \leq 10^3$.
• $20/30$ testcase còn lại tuân theo các ràng buộc gốc nêu trên.

Đầu vào: Lịch trình di chuyển được mô tả như sau:

• Dòng đầu tiên chứa một chuỗi ký tự biểu diễn ngày bắt đầu lên lịch trình (định dạng DD/MM/YYYY).
• Dòng thứ hai chứa một số nguyên N — số ngày bạn di chuyển bằng xe buýt.
• Trong N dòng tiếp theo, dòng thứ $i$ có định dạng:
  • Số đầu tiên d_i — ngày thứ $d_i$ tính từ ngày bắt đầu lịch trình (ví dụ: nếu ngày bắt đầu là 01/02/2000 thì 01/02/2000 là ngày thứ 1, 02/02/2000 là ngày thứ 2, ...).
  • Số tiếp theo k_i — số chuyến đi trong ngày thứ $i$. Tiếp theo là k_i số nguyên biểu diễn quãng đường của từng chuyến đi.
• Thông tin giá vé được cho trong 5 dòng tiếp theo: dòng đầu tiên chứa 3 số nguyên là giá vé loại 1 cho các chặng ngắn, chặng trung bình và chặng dài; 4 dòng tiếp theo lần lượt chứa giá của vé ngày, vé tuần, vé tháng và vé năm.

Đầu ra: In ra một số nguyên duy nhất là tổng chi phí tối ưu (nhỏ nhất) để mua vé.

Giải thích: Dòng đầu tiên cho biết ngày bạn bắt đầu lên kế hoạch đi xe buýt là thứ Sáu, 09/09/2022; 5 dòng tiếp theo tương ứng với kế hoạch đi xe buýt trong 5 ngày. Cụ thể:

• Ngày thứ 1 (09/09/2022): bạn đi 3 chuyến xe buýt với quãng đường lần lượt là 5, 8 và 6 km.
• Các ngày thứ 2, 3 và 4: bạn không có kế hoạch đi xe buýt.
• Ngày thứ 5 (thứ Ba tuần tiếp theo): bạn có 1 chuyến đi với quãng đường 12 km.
• Các ngày thứ 6, 7, 8 và 9: bạn không có kế hoạch đi xe buýt.
• Cuối cùng, vào các ngày thứ 10, 11 và 12: mỗi ngày bạn đi 1 chuyến với quãng đường lần lượt là 3, 3 và 2 km.

Để tối ưu chi phí cho ví dụ trên, bạn nên mua vé loại 1 cho toàn bộ các chuyến đi. Tổng chi phí tối ưu nhất là 34000.

Ví dụ 1:

Đầu vào:

09/09/2022
5
1 3 5 8 6
5 1 12
10 1 3
11 1 3
12 1 2
3000 5000 10000
20000
100000
1500000
10000000

Đầu ra:

34000