В стране УмомНеПонятии кризис.
Курсы валют стремительно меняются, и иногда в разных банках они существенно
отличаются.
Вы – житель этого многострадального государства. И в данный
момент у Вас имеется некая сумма денег в местной валюте (серебряных дырках). А
ещё у вас есть данные о курсе покупки и продажи самой популярной и стабильной
валюты – рубля, - в серебряных дырках. Вам необходимо определить, какую
максимальную прибыль Вы сможете извлечь из ваших накоплений, купив на них рубли
подешевле в одном банке, и продав подороже в другом. Если при данных курсах валютные операции
невыгодны, вы воздержитесь от них, получив прибыль 0.
Входные данные
Первая строка – два целых числа: D (имеющееся у Вас количество серебряных дырок) и N (количество
банков, сведения о курсах в которых у Вас есть). 1<=D<=100000, 1<=N<=100.
Каждая из последующих N строк содержит пару натуральных чисел Bi и Si, курс продажи и
покупки рубля в серебряных дырках в банке i.
Выходные данные
В единственной строке - одно целое неотрицательное
число P – максимальная
прибыль, которую вы можете получить, в серебряных дырках.
Пример входных и
выходных данных
|
Вход
|
Выход
|
|
50 3
27 22
23 20
29 26
|
6
|
Для отправки решений необходимо