Удеякому місті будинки, що знаходяться по одну сторону єдиної вулиці, пронумеровані послідовними числами від 1 до n. відстань між сусідніми будинками достатньо велика, тому мешканці звикли пересуватись по місту на маршрутних таксі, яких усього м. поїздка по одному маршруту на будь-яку відстань коштує лише один долар, але кожне таксі зупиняється тільки біля строго визначених (але не менше двох) будинків. на зупинки вказує номер маршруту — а в (а — найменший номер будинку, де зупиняється таксі, в — період зупинок). наприклад, маршрутне таксі з номером 2 3 при n=11 зупиняється так: 2 5 8 11 8 5 тому деякі будинки можуть бути незадіяними. знаючи значення n і м та номери всіх маршрутів, можна знайти скільки найменше доларів потрібно витратити, щоб дістатися з першого до n-гo будинку або вивести 0, якщо це неможливо. числові значення n, м, а і в — натуральні, 1˂n˂200, 1˂a,b,m˂20. вхідні дані в одному рядку міститься два натуральних числа у вказаному порядку, розділені пропуском n i m. у наступних n рядках вводяться числа а і в – параметри кожного маршрутного таксі. вихідні дані вивести єдине число: найменші витрати або 0, якщо визначити витрати неможливо