Canadian Informatics Workshop 2026: Day 2, Problem 2

There will be ~N~ customers coming to visit your video store. Customer ~i~ will arrive at the start of the ~l_i~-th minute and leave at the end of the ~r_i~-th minute. You can also do ~M~ store tasks, labeled from ~1~ to ~M~. To complete any task, you must have already completed each task with a lower label. Each task takes ~K~ seconds to complete, must be worked on in one continuous interval, and can be completed at most once. You cannot serve customers when working on these tasks, and you cannot work on these tasks when serving customers.

By serving customer ~i~ during the entire duration of their visit, you get ~v_i~ coins. Note that multiple customers may visit the store at any time, and you can serve any number of customers simultaneously. By completing task ~i~, you get ~w_i~ coins.

You begin operating the store at the start of the ~1~st minute. Maximize the number of coins you can get by the end of the ~T~-th minute.

Input Specification

The first line contains four integers ~N~, ~M~, ~T~, and ~K~ (~1 \le K \le T~).

Each of the next ~N~ lines contains three integers ~l_i~, ~r_i~, and ~v_i~ (~1 \le l_i \le r_i \le T, 1 \le v_i \le 10^9~).

The next line contains ~M~ integers ~w_1,\ldots,w_M~ (~1 \le w_i \le 10^9~).

The following table shows how the available 25 marks are distributed:

Marks Awarded	Bounds on ~N~	Bounds on ~M~	Bounds on ~T~	Additional Constraints
2 marks	~1 \le N \le 10~	~1\le M \le 300~	~1 \le T \le 10^9~	None
3 marks	~1 \le N \le 300~	~1\le M \le 300~	~1 \le T \le 600~	~l_i = r_i~
3 marks	~1 \le N \le 300~	~1\le M \le 300~	~1\le T \le 600~	No more than one customer will visit at any time
4 marks	~1\leq N \leq 300~	~1\le M \le 300~	~1 \le T \le 600~	None
4 marks	~1\leq N \leq 300~	~1\le M\le 300~	~1 \le T \le 10^9~	~l_i = r_i~
4 marks	~1\leq N \leq 300~	~1\le M \le 300~	~1 \le T \le 10^9~	No more than one customer will visit at any time
5 marks	~1\leq N \leq 300~	~1\le M \le 300~	~1 \le T \le 10^9~	None

Output Specification

Output a single integer representing the maximum number of coins you can get by the end of the ~T~-th minute.

Sample Input

2 2 7 3
3 4 8
4 5 4
6 7

Sample Output

14

Explanation for Sample Output

There are several possible ways to earn coins, such as serving customers ~1~ and ~2~ from the start of the ~3~rd minute to the end of the ~5~th minute for ~8+4=12~ coins or completing both tasks in ~6~ minutes for ~6+7=13~ coins. The maximum number of coins can be achieved by serving customer ~1~ from the start of the ~3~rd minute to the end of the ~4~th minute and then completing task ~1~ from the start of the ~5~-th minute to the end of the ~7~th minute for ~8+6=14~ coins.