Seminars Scheduling

Quido has enrolled an advanced course in early mesozoic paleontology. The course consists of many different seminars. Some seminars are held in Czech, other seminars are held in English. There is a fixed prescribed number of seminars in Czech and in English which Quido has to attend in order to complete the course successfully. The number of prescribed seminars is rather high. Therefore, Quido wants to minimize the total time spent on seminars so that he has enough time to study the fossils in the museum and to visit the excavation sites in the country.
Fortunately, the choice of particular seminars is entirely up to Quido. There is only one significant limiting factor. The seminars which Quido takes cannot overlap as he is expected to be present at each seminar from its very beginning to its very end. Each seminar is a one-time event and its start time and end time are fixed.

� � �


Image 1. Timetables of seminars. Czech seminars are in blue, English Seminars are in red. Scheme a), b), c) depicts, in this order, Example 1, 2, 3 bellow. Possible choices of seminars which lead to the minimum total time are depicted by bold outline of particular seminars.

The task

A complete list of seminars is given. A seminar is described by its start and end times and by the language in which it is held. Also, a number of seminars in Czech and in English which Quido has to attend is given. Quido cannot attend any two seminars overlapping in time. A pair of seminars in which the end time of the first one is equal to the start time of the second one is not considered to be overlapping.
Find the shortest possible total time which Quido has to spend on seminars to complete the course.

Input

The first line contains three positive integers N, C, E separated by space. N represents the number of seminars available, C and E represent the number of seminars in Czech and in English which Quido has to attend. Next, there are N lines each of which describes one seminar. A line contains three integers T1, T2, L separated by space. Value of T1 resp. T2 denote the start resp. the end time of a seminar, 0 ≤ T1 < T2 ≤ 105. Value L is 0 or 1, Czech is represented by 0, English is represented by 1. Duration of the seminar is equal to the value T2−T1. The seminars are listed in no specific order.
It holds, 0 < C + E ≤ N ≤ 1700.

Output

The output consists of one text line containing one non-negative integer equal to the minimum possible total time spent on C Czech and E English non-overlapping seminars.
It is guaranteed that the solution exists in all cases presented in this problem.

Example 1

Input
6 1 1
1 3 0
2 10 1
2 5 0
3 7 1
4 11 0
6 11 1

Output
6
The data and the solution of Example 1 are depicted in Image 1a).

Example 2

Input
12 2 2
1 3 0
2 10 1
2 5 0
2 7 1
4 11 0
6 11 1
8 13 0
10 13 1
10 13 0
12 15 1
14 17 0
16 19 1

Output
15
The data and the solution of Example 2 are depicted in Image 1b).

Example 3

Input
50 5 3
6 10 1
27 31 1
10 14 1
28 32 1
5 7 1
24 26 1
7 9 1
13 15 1
23 26 1
19 22 1
17 20 1
20 23 0
11 14 1
16 19 1
25 29 0
26 28 1
15 18 0
29 32 0
26 30 1
0 3 0
10 14 1
28 32 0
22 25 0
20 24 1
28 31 1
26 30 1
26 29 1
1 3 1
11 13 1
7 9 0
7 10 0
0 3 1
2 5 0
10 13 1
9 12 0
8 11 1
29 31 0
25 28 1
8 12 0
7 10 1
5 7 1
19 21 0
15 19 1
7 9 0
27 31 1
1 5 1
18 20 0
17 19 0
0 3 0
15 17 0

Output
16
The data and the solution of Example 3 are depicted in Image 1c).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set