#P7652. [2018年杭电多校]Videos

    ID: 7665 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>图论贪心动态规划数据结构CF2200网络流

[2018年杭电多校]Videos

L. Videos

Problem Description

C-bacteria takes charge of two kinds of videos: ’The Collection of Silly Games’ and ’The Collection of Horrible Games’.

For simplicity’s sake, they will be called as videoA and videoB.

There are some people who want to watch videos during today, and they will be happy after watching videos of C-bacteria.

There are n hours a day, m videos are going to be show, and the number of people is K.

Every video has a type(videoA or videoB), a running time, and the degree of happiness after someone watching whole of it.

People can watch videos continuous(If one video is running on 2pm to 3pm and another is 3pm to 5pm, people can watch both of them).

But each video only allows one person for watching.

For each person, every adjacent pair of watched videos of the same type incurs a penalty of WW, even if there is a time gap between them. The first video incurs no penalty. A person may watch no videos.

For example, if the order of video is A, B, A, B, ... or B, A, B, A, B, ..., he won’t lose happiness; But if the order of video is ’A, B, B, B, A, B, A, A’, he will lose 3W happiness.

Now you have to help people to maximization the sum of the degree of happiness.

输入格式

Multiple query.

On the first line, there is a positive integer T, which describe the number of data. Next there are T groups of data.

for each group, the first line have four positive integers n, m, K, W : n hours a day, m videos, K people, lose W happiness when watching same videos).

and then, the next m line will describe m videos, four positive integers each line S, T, w, op : video is the begin at S and end at T, the happiness that people can get is w, and op describe it’s type(op=0 for videoA and op=1 for videoB).

There is a blank line before each groups of data.

1≤T≤201\le T\le20, 1≤n,m,K≤2001\le n,m,K\le200, 1≤W≤201\le W\le20, 1≤S<T≤n1\le S<T\le n, W≤w≤1000W\le w\le1000, op∈{0,1}op\in\{0,1\}. Here the test count and a video end time are both denoted by TT in the source; they are separate quantities.

输出格式

Your output should include T lines, for each line, output the maximum happiness for the corresponding datum.

样例输入

2
10 3 1 10
1 5 1000 0
5 10 1000 1
3 9 10 0
10 3 1 10
1 5 1000 0
5 10 1000 0
3 9 10 0

样例输出

2000
1990