Вартість авіаквитків
Ціни на авіаквитки можуть значно змінюватися з тижня в тиждень, що часто викликає розчарування у мандрівників. Деякі з них шкодують, що купили квитки занадто рано, коли ціни падають після покупки, а інші — що купили занадто пізно, коли ціни підвищуються перед покупкою. Зрештою, ніхто не задоволений, окрім авіакомпаній.
Причина цього явища полягає в тому, що авіакомпанії динамічно змінюють ціни на квитки залежно від кількості доступних місць і часу до польоту. Наприклад, якщо на рейс залишилося мало місць, ціни можуть бути високими, але в останні тижні перед польотом вони можуть знизитися, щоб заповнити порожні місця. Авіакомпанії прагнуть максимізувати дохід від кожного рейсу.
Вас найняла компанія International Contrived Pricing Corporation (ICPC) для встановлення цін на квитки щотижня для авіакомпаній. Авіакомпанії зібрали історичні дані і мають точні прогнози щодо кількості місць, які будуть продані за певною ціною з певною кількістю тижнів до польоту. Враховуючи кількість залишених місць і тижнів до рейсу, вам потрібно встановити ціну квитка на поточний тиждень, щоб максимізувати загальний дохід від продажу квитків з цього тижня до польоту. Можна припустити, що кількість проданих квитків точно відповідатиме прогнозу, якщо вистачає місць. В іншому випадку всі залишені місця будуть продані. Також можна припустити, що оптимальні ціни на квитки будуть обрані на кожен з тижнів, що залишилися до польоту.
Зверніть увагу, що вищі ціни не завжди означають менший продаж квитків. Іноді вищі ціни можуть навіть збільшити продажі, оскільки мандрівники можуть побоюватися подальшого зростання цін.
Вхідні дані
Перший рядок містить два цілі числа n і w (0 < n ≤ 300, 0 ≤ w ≤ 52) — кількість залишених місць і число тижнів до польоту. Наступні w + 1 рядок містять прогнози для w тижнів, w - 1 тижнів і так далі до 0 тижнів (тобто останнього тижня) до польоту. Кожен з цих рядків починається з числа k (0 < k ≤ 100) — кількість цін на поточний тиждень. Далі йдуть k цілих чисел 0 < p[1] < ... < p[k] < 1000, що представляють ціни в доларах. Потім йдуть k цілих чисел s[1], ..., s[k] (0 ≤ s[i] ≤ n), що вказують кількість квитків, які будуть продані за відповідними цінами.
Вихідні дані
У першому рядку виведіть максимальний загальний дохід, який авіакомпанії можуть отримати від продажу квитків з поточного тижня до польоту. У другому рядку виведіть ціну квитка, яку слід встановити на поточний тиждень (w тижнів до польоту), щоб досягти цього максимуму.
Якщо існує кілька варіантів цін на квитки, які досягають максимуму, виберіть найменшу ціну квитка на тиждень w.