Background

Translated from COCI 2023/2024 Contest #3 Task 2 "Vrsar".

Problem Description

Vrsar is a seaside town consisting of $n$ small hills. Surprisingly, when viewed from the coast, the $n$ hills form a line, and the distance from the $i$-th hill to the coast is $x_i$ meters. At the top of each hill, there is an ice rink. All rinks open at the same time every day, but their closing times differ. The $i$-th rink is open for $t_i$ minutes.

Iva and Mia have arrived in Vrsar, and they will stay for $m$ days. They love ice skating and want to spend every day in Vrsar skating. At the start of day $i$, they are $a_i$ meters from the coast. As soon as the rinks open, they begin their skating trip. They need to walk to a rink, and their walking speed is $1$ meter per minute.

They are very fit, so they do not need extra time to climb up a hill. Once they reach the rink at the top, they can skate for any length of time until the rink closes. However, going downhill is not as easy as going uphill: because it is raining and the paths are slippery, they need $s_i$ time to walk down hill $i$. After coming down from one hill, they can go to another hill.

Iva and Mia want to know the maximum total time they can skate each day. Each day, they may visit any number of rinks. Since they want to spend as much time skating and as little time computing as possible, they ask you for help. Help them solve this problem.

Note: If there is a hill at Iva and Mia’s starting position in the morning, then they are at the foot of that hill.

Input Format

The first line contains two integers $n,m$ ($1 \le n,m \le 10^5$), representing the number of hills and the number of days.

The next $n$ lines each contain three integers $x_i,t_i,s_i$ ($0 \le x_i,t_i,s_i \le 10^9$), representing the distance of hill $i$ from the coast, the rink closing time, and the time required to walk down the hill.

The third line contains $m$ integers $a_i$ ($1 \le a_i \le 10^9$), representing Iva and Mia’s distance from the coast at the start of day $i$.

Output Format

Output one line with $m$ integers. The $i$-th integer is the maximum total skating time Iva and Mia can achieve on day $i$.

3 1
3 7 0
6 11 3
10 13 5
1

6

3 2
5 10 3
3 6 1
1 5 0
0 3

5 8

1 3
3 3 3
0 1 2

0 1 2

Hint

Sample Explanation 1

Iva and Mia start at position $1$, walk $2$ minutes to the hill at position $3$, and skate for $5$ minutes. Then they spend $0$ minutes walking down, continue walking for $3$ minutes to the rink on the hill at position $6$, and skate for $1$ minute.

In total, they skate for $6$ minutes.

Subtasks

Translated by ChatGPT 5