Xəzinə qutusu

Verilmiş boş pul qabının çəkisi E və onun içindəki pullarla birlikdə çəkisi F olaraq verilir. Pul qabında N növ sikkə ola bilər və hər növ sikkə üçün bir sikkənin dəyəri P_i və çəkisi W_i məlumdur. Pul qabında ola biləcək minimum və maksimum pul məbləğini müəyyən edin.

Giriş verilənləri

Birinci sətirdə E və F ədədləri verilir. İkinci sətirdə N ədədi, növbəti N sətirdə isə hər bir sikkə növü üçün iki ədəd, P_i və W_i verilir. Burada 1 ≤ E ≤ F ≤ 10000, 1 ≤ N ≤ 500, 1 ≤ P_i ≤ 50000, 1 ≤ W_i ≤ 10000 və bütün ədədlər tam ədədlərdir.

Çıxış verilənləri

İki ədəd boşluqla ayrılmış şəkildə çıxarılmalıdır - minimum və maksimum məbləğlər. Əgər pul qabı verilmiş növ sikkələrlə dəqiq müəyyən edilmiş çəkiyə malik ola bilmirsə, "This is impossible." çıxarın.

Nümunələr