Daily Running Check-In Challenge

Little T is passionate about running. To make running more interesting, he developed a software called "Daily Run Check-In" that allows users to check in by running every day. In the trial run, which lasts for n days (numbered from 1 to n), the following rules apply for Da Y:

• If on any day Da Y chooses to check in (i.e. go for a run), his energy decreases by d.
• He starts with an energy of 0 and his energy may become negative during the trial.
• He is not allowed to check in (run) for more than k consecutive days. In other words, there should be no period of k+1 consecutive days where he runs.

In addition, Little T designed m challenges. The i-th challenge is described by three positive integers \(x_i, y_i, v_i\), meaning that if on day \(x_i\) the user has been checking in (running) for at least \(y_i\) consecutive days (i.e. from day \(x_i - y_i +1\) to day \(x_i\) all days are check-ins), then the user will receive a reward that increases his energy by \(v_i\). Note that multiple challenges can occur on the same day, and if the condition is met for a challenge, the corresponding \(v_i\) is added to the energy.

Your task is to help Da Y determine the maximum energy he can achieve at the end of the n-day trial by choosing on which days to check in (run) subject to the given rules.

inputFormat

The input begins with a line containing three space-separated integers n, k, and d — the number of days, the maximum allowed consecutive check-ins, and the energy cost for a check-in, respectively.

The next line contains a single integer m denoting the number of challenges. Each of the following m lines contains three space-separated positive integers \(x_i\), \(y_i\), and \(v_i\), where:

• \(x_i\) (1 ≤ \(x_i\) ≤ \(n\)) is the day of the challenge.
• \(y_i\) is the minimum number of consecutive check-ins required by day \(x_i\) to earn the reward.
• \(v_i\) is the energy boost if the challenge condition is met.

outputFormat

Output a single integer representing the maximum energy Da Y can have at the end of n days.

sample

5 2 10
2
3 2 50
5 1 20

40