Изградена е нова велосипедска патека која е долга M метри. На патеката се поставени канделабри за осветлување. Но, сите тие канделабри не се вклучени затоа што потрошувачката на енергија е голема.

За секоја канделабра i, i=1…N дадени се информациите: Xi – целобројно растојание на канделабрата од почетокот на патеката, Ci – дневна потрошувачка на канделабрата изразени во денари, Ri – радиусот на осветлување на канделабрата (колку метри пред и после канделабрата патеката е осветлена со канделабрата). Познато е и дека нема должина (парче) од патеката која може да биде осветлена со повеќе од една канделабра.

Градската управа решила да вклучи дел од канделабрите. Изборот за тоа кои канделабри ќе бидат вклучени се базира на следните барања:

- Должината на осветлениот дел од патеката е максимална.
- Дневната потрошувачка (во денари) вкупно за сите избрани канделабри да биде најмногу К денари.

Градската управа сака да знае кои се тие канделабри кои треба да бидат вклучени за да бидат задоволени нивните барања. Да се земе дека за избор на канделабрите секогаш ќе има само едно можно решение.

Коста е добар програмер и тој знае кои се тие канделабри, но не сака да каже. Единствено нешто што кажал е колкава ќе биде должината на најдолгиот континуиран неосветлен дел од патеката ако се вклучат канделабрите според барањата, бидејќи негодувал околу тоа.

Вие треба да покажете дека сте добар програмер како и Коста и дека знаете како да го решите дадениот проблем. Затоа, ваша задача е да најдете она што Коста веќе го знаел и она што Коста веќе го кажал: прво вкупната должина на осветлениот дел од патеката, а потоа должината на најдолгиот континуиран неосветлен дел од патеката.

Влез

Во првиот ред се запишани два цели броја M (1≤M≤10000) и K (1≤K≤1000) кои ја претставуваат должината на патеката и максималниот дневен трошок. Во следниот ред е запишан бројот на канделабри N (1≤N≤100). Во секој следен ред се запишани информации за секоја следна канделабра: Xi (0≤Xi≤М≤10000) - целобројно растојание од почетокот на патеката, Ci (1≤Ci≤100) - дневна потрошувачка на i-тата канделабра и Ri(1≤Ri≤10) - радиусот на осветлување на i-тата канделабра.

Излез

Вкупната должина на осветлениот дел од патеката и должината на најдолгиот континуиран неосветлен дел од патеката ако се вклучени канделабрите со кои најголем дел од патеката е осветлена, а дневната потрошувачка вкупно за сите вклучени канделабри е најмногу K. Броевите се напишани во еден ред и се одвоени со едно празно место.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
10 7
2
2 2 1
7 4 2

излез
6 2

влез
10 3
3
2 2 1
6 1 1
8 3 1

излез
4 3

влез
10 7
3
3 3 1
5 2 1
9 6 2

излез
4 4

влез
10 2
1
0 3 1

излез
0 10

Објаснување за првиот тест пример: Патеката има должина 10, а максималната потрошувачка е 7. Првата канделабра е поставена на растојание 2 од почетокот на патеката, дневната потрошувачка е 2 и радиусот на осветлување е 1. Ова значи дека со оваа канделабра би се осветлила патеката на интервал [1,3] (канделабрата е во точката 2, а радиусот е 1). Втората канделабра би ја осветлила патеката на интервал [5,9] (канделабрата е во точката 7, а радиусот е 2). Во овој пример може да се вклучат и двете канделабри и нивната дневна потрошувачка би била 6, што градската управа може да го дозволи. Во овој случај вкупната должина на осветлениот дел од патеката е 6. Неосветлени би биле интервалите [0,1],[3,5] и [9,10]. Најдолгиот од овие е вториот и има должина 2.

Објаснување за вториот тест пример: Ако се вклучат првата и втората канделабра тогаш потрошувачката ќе биде 2+1=3. Во овој случај патеката ќе биде осветлена на интервалите: [1,3] и [5,7] т.е. осветлени ќе бидат 4 метри. Ако се вклучи само третата канделабра за која се потребни 3 денари тогаш осветлен ќе биде интервалот [7,9]. И во двата случаи имаме доволно финансии (K=3), но во првиот случај ќе бидат осветлени 4, а во вториот 2 метри од патеката. Оптималното осветлување ќе биде со вклучување на првите две канделабра. Во овој случај најдолгиот неосветлен дел од патеката е 3 ([7,10]).

Објаснување за третиот тест пример: Најголем дел од патеката ќе биде осветлен со најмногу 7 денари ако се вклучат првата и втората канделабра. Во овој случај осветлен ќе биде интервалот [2,6] т.е. 4 метри. Ако се одлучиме да ја вклучиме само третата канделабра тогаш осветлен ќе биде интервалот [7,10] т.е. 3 метри (канделабрата е во 9, радиусот е 2 и патеката е долга 10 метри). Во случајот каде се вклучени првата и втората канделабра најдолгиот неосветлен дел од патеката ќе биде на интервалот [6,10] кој има должина 4.

Објаснување за четвртиот тест пример: Единствената канделабра која е поставена има дневна цена 3 и е поскапа од најголемата дозволена цена K=2. Затоа не може да се вклучи ниту една канделабра (осветлени ќе бидат 0 метри), а целата патека која има должина 10 ќе биде неосветлена.