Пірат знайшов на захопленому кораблі \(N\) дорогоцінних предметів, кожен із яких має деяку вартість (\(V_i\) для предмета з номером \(i\)). Відома також вага кожного з предметів (\(W_i\) для предмета з номером \(i\)). Під час бою захоплений корабель отримав серйозні пошкодження і ось-ось затоне. Пірат може відвезти на шлюпці на свій корабель лише \(C\) кілограмів вантажу.

Знайдіть найбільшу вартість предметів, які може забрати пірат.

Формат вхідних даних

У першому вхідному рядку записано вантажопідйомність \( C\) шлюпки пірата в кілограмах ( \(1 \le C \le 5000\) ).

У другому рядку – кількість предметів \(N\) (\( 1 \le N \le 100 \)).

У наступних \(N\) рядках записані дані про предмети у форматі

<вага> <вартість>

Формат вихідних даних

Програма має вивести одне число: найбільшу вартість предметів, які може забрати пірат.

Приклад вхідних даних

8
4
1 15
5 10
3 9
4 5

Приклад вихідних даних

29