Юбиляр К. хочет отметить свой юбилей в приятной компании, состоящей из людей, психологически совместимых друг с другом. Являясь, кроме того, человеком не без предрассудков, юбиляр при составлении списка приглашенных намерен учесть также их возраст.

Имеется список лиц, претендующих на роль приглашенных на юбилейный вечер. Требуется составить программу, которая позволит получить список приглашенных, причем их суммарный возраст не должен превышать заданного числа S. При составлении списка следует исходить из таблицы психологической совместимости конкретных лиц. Предполагается собрать наиболее многочисленную компанию, суммарный возраст которой был бы максимально близок к S.

В первой строке входного файла COMPANY.IN находится натуральное число S, S<=10000, во второй строке – натуральное число n, n<=100. Далее следуют n строк, в каждой из которых располагаются разделенные пробелом фамилия человека и его возраст (число полных лет). В следующих строках записаны разделенные пробелом пары номеров психологически несовместимых лиц.

В первой строке выходного файла COMPANY.OUT должно находиться число, соответствующее наибольшему числу гостей, которые могут быть приглашены на юбилей. Далее выводится список приглашенных, содержащий в каждой строке разделенные пробелом фамилию гостя и его возраст. Последняя строка должна содержать значение суммарного возраста гостей.

При наличии нескольких вариантов ответа вывести любой из них.