Степан — опытный участник олимпиад. У него есть n кубков за олимпиады по физике и m — по информатике. Каждый кубок характеризуется двумя параметрами — своей значимостью ci и шириной wi.
Степан решил выставить часть своих кубков на полке общей ширины d так, чтобы:
- на полке был хотя бы один кубок по физике и хотя бы один кубок по информатике,
- суммарная ширина выставленных кубков не превышала d,
- от каждого предмета были выставлены несколько самых значимых кубков (то есть, если по какому-то предмету выставлен кубок с значимостью x, то должны быть выставлены все кубки по этому предмету, чья значимость превышает x).
Перед вами стоит задача определить максимально возможную суммарную значимость кубков, которые Степан может выставить на полку ширины d, учитывая все описанные выше условия.
Выходные данные
Выведите максимально возможную суммарную значимость кубков, которые Степан может выставить на полку ширины d, учитывая все необходимые требования.
Если не существует ни одного способа выставить кубки, выведите 0.
Примечание
В первом примере у Степана есть всего один кубок по информатике, который обязательно нужно выставить. Его значимость равна 3, а ширина 2, поэтому после его выставления ширина оставшегося места на полке равна 6. Также Степан должен выставить второй кубок с шириной 5 по физике, так как он самый значимый (его значимость равна 5). После этого на полку больше нельзя поставить ни одного кубка. Поэтому максимальная суммарная значимость выставленных кубков равна 8.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 8
4 2
5 5
4 2
3 2
|
8
|
|
2
|
4 3 12
3 4
2 4
3 5
3 4
3 5
5 2
3 4
|
11
|
|
3
|
2 2 2
5 3
6 3
4 2
8 1
|
0
|