Имеется набор данных, состоящий из N пар натуральных чисел. Напишите программу, которая выполняет следующее задание.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел удовлетворяла
хотя бы одному из следующих условий:
- не делилась на число X;
- при переводе в P-ую систему счисления не оканчивалась на цифру С (0 <= C < P).
Гарантируется, что искомую сумму получить можно.
Среди всех возможных вариантов выберите такой, чтобы сумма была максимально возможной.
В качестве ответва программа должна напечатать одно число – максимально возможную сумму,
соответствующую условиям задачи.
Входные данные
В первой строке набора данных записаны четыре натуральных числа N, X, P, C .
Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 10000.
Все числа представлены в десятичной записи.
Примеры организации входных данных:
| Входные данные |
Выходные данные |
Пояснения |
3 9 8 4
4 252
108 180
36 36 |
|
Для представленных входных данных
надо выбрать числа 36, 73, 62.
Их сумма будет равна 171.
Число 171 кратно 9 (171=9*29),
но 17110=2538
(последняя цифра не равна 4) |
3 9 8 4
4 252
108 180
36 36 |
|
Для представленных входных данных
надо выбрать числа 4, 180, 36.
Их сумма будет равна 220.
Число 22010=3348
(последняя цифра не равна 4),
но 220 не кратно 9 (220=9*24+4)?? |
3 9 8 4
36 26
73 31
62 18 |
171 |
Для представленных входных данных
надо выбрать числа 36, 73, 62.
Их сумма будет равна 171.
Число 171 кратно 9 (171=9*29),
но 17110=2538
(последняя цифра не равна 4) |
В ответе укажите два числа:
В первой строке - значение искомой суммы для файла А,
во второй строке - значение искомой суммы для файла Б
Ограничения на значения:
Файл А: N<=100, 1< X <100, 1< P <17 , 0<= C < P;
Файл Б: N<=106, 1< X < 106, 1<P< 105, 0<= C < P.
Файл А Файл Б