Alladinin Çantası

Ələddin mağarada xəzinə ilə qarşılaşanda köhnə qaralmış lampanı götürmədi. Bunun əvəzinə, qızıl sikkələri və qiymətli daşları çantasına yığmağa başladı. Amma o, hər şeyi götürə bilməzdi, çünki çantanın çox ağır yükü daşıması mümkün deyildi.

O, dəfələrlə bəzi əşyaları çıxarıb onların yerinə başqalarını qoyaraq, çantadakı əşyaların ümumi dəyərini artırmağa çalışırdı.

Ələddinin çantasına yerləşdirə biləcəyi əşyaların maksimum dəyərini tapmaq lazımdır.

Tutaq ki, mağarada $n$ müxtəlif növ əşya var və hər növ əşyaların sayı məhduddur. Çantanın daşıya biləcəyi maksimum çəki $s$-ə bərabərdir. Hər bir $i$ növ əşyanın çəkisi $w_i$ və dəyəri $v_i(i=1,2,...,n)$-dir.

Giriş verilənləri

Birinci sətirdə iki natural ədəd $s$ və $n(1\le s\le 250,1\le n\le 35)$ verilir — çantanın daşıya biləcəyi maksimum çəki və əşyaların növlərinin sayı. Növbəti $n$ sətirin hər biri iki ədəd $w_i$ və $v_i(1\le w_i\le 250,1\le v_i\le 250)$ — $i$ növ əşyanın çəkisi və dəyərini göstərir.

Çıxış verilənləri

Çəkisi $s$-i aşmayan əşyaların maksimum dəyərini çıxarın.

Nümunələr