Андрей Викторович уже третий год проводит тренировки в олимпиадном кружке СГАУ. В этом году он узнал, что, как опытный тренер, он может претендовать на грант университета Силопонни. Для этого ему надо провести n тренировок, в каждой из которых должно принять участие не менее m студентов. Кроме того, всего в тренировках должны поучаствовать не менее k различных студентов.
Также Андрей Викторович читает лекции в университете, на которые ходят a студентов. В конце семестра Андрей Викторович ставит экзамен автоматом тем студентам, которые набрали достаточное количество бонусных баллов. Одним из способов получения бонусных баллов является участие в тренировках.
Впрочем, студенты полагают, что участие в тренировках нужно не только им, но и Андрею Викторовичу, поэтому j-й студент согласен прийти не более чем на cj тренировок, причём только в том случае, если получит за каждую из них по dj бонусных баллов. Некоторые студенты являются поклонниками Андрея Викторовича (они даже организовали «Gaidel Fan Club»), поэтому они готовы приходить на тренировки, не получая бонусных баллов.
Андрей Викторович волен выбирать, каких именно студентов и на какую тренировку он позовёт. Студенты, которых Андрей Викторович не позвал, на тренировку не придут и бонусных баллов не получат.
Конечно, Андрей Викторович хочет получить грант. Но поскольку он считает, что всех студентов следовало бы отчислить, он хочет выдать минимально возможное количество бонусных баллов. Помогите ему определить это количество. Если выполнить все условия гранта нельзя, выведите сообщение о том, что Андрей Викторович плохой тренер.
В первой строке содержатся три целых числа n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ k ≤ 105) — количество тренировок, минимальное количество студентов на одной тренировке и минимальное количество студентов, которые должны принять участие хотя бы в одной тренировке.
Во второй строке содержатся единственное целое число a (1 ≤ a ≤ 105) — количество студентов, у которых читает лекции Андрей Викторович.
В каждой из следующих a строк содержится по два целых числа ci и di (1 ≤ ci ≤ 105, 0 ≤ di ≤ 106) — максимальное количество тренировок, которое согласен посетить i-й студент, и количество бонусных баллов, которое он хочет получить за каждую тренировку.
В первой строке выведите единственное целое число — минимальное количество бонусных баллов, которые придётся выдать Андрею Викторовичу, чтобы получить грант.
Если же Андрею Викторовичу не удастся получить грант, выведите вместо числа _Bad Coach_ (в точности, как написано).
## Входные Данные
В первой строке содержатся три целых числа n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ k ≤ 105) — количество тренировок, минимальное количество студентов на одной тренировке и минимальное количество студентов, которые должны принять участие хотя бы в одной тренировке. Во второй строке содержатся единственное целое число a (1 ≤ a ≤ 105) — количество студентов, у которых читает лекции Андрей Викторович.В каждой из следующих a строк содержится по два целых числа ci и di (1 ≤ ci ≤ 105, 0 ≤ di ≤ 106) — максимальное количество тренировок, которое согласен посетить i-й студент, и количество бонусных баллов, которое он хочет получить за каждую тренировку.
## Выходные Данные
В первой строке выведите единственное целое число — минимальное количество бонусных баллов, которые придётся выдать Андрею Викторовичу, чтобы получить грант.Если же Андрею Викторовичу не удастся получить грант, выведите вместо числа _Bad Coach_ (в точности, как написано).
## Примеры
Входные данные4 3 554 04 04 03 13 2Выходные данные3Входные данные4 3 654 04 04 03 13 2Выходные данныеBad Coach
[samples]
**Definitions**
Let $ n, m, k \in \mathbb{Z}^+ $ denote the number of trainings, minimum students per training, and minimum distinct students across all trainings, respectively.
Let $ a \in \mathbb{Z}^+ $ denote the number of students.
For each student $ i \in \{1, \dots, a\} $:
- $ c_i \in \mathbb{Z}^+ $ is the maximum number of trainings student $ i $ will attend.
- $ d_i \in \mathbb{R}_{\geq 0} $ is the bonus points demanded per training attended.
Let $ x_{i,j} \in \{0,1\} $ indicate whether student $ i $ attends training $ j $ ($ j \in \{1, \dots, n\} $).
Let $ y_i \in \mathbb{Z}_{\geq 0} $ denote the number of trainings student $ i $ attends: $ y_i = \sum_{j=1}^n x_{i,j} $.
Let $ B = \sum_{i=1}^a d_i \cdot y_i $ be the total bonus points awarded.
**Constraints**
1. $ 1 \leq n \leq 10^5 $, $ 1 \leq m \leq k \leq 10^5 $, $ 1 \leq a \leq 10^5 $
2. $ 1 \leq c_i \leq 10^5 $, $ 0 \leq d_i \leq 10^6 $ for all $ i \in \{1, \dots, a\} $
3. For each training $ j \in \{1, \dots, n\} $: $ \sum_{i=1}^a x_{i,j} \geq m $
4. $ \left| \left\{ i \in \{1, \dots, a\} \mid y_i \geq 1 \right\} \right| \geq k $
5. $ y_i \leq c_i $ for all $ i \in \{1, \dots, a\} $
**Objective**
Minimize $ B = \sum_{i=1}^a d_i \cdot y_i $, subject to the above constraints.
If no feasible assignment exists, output **Bad Coach**.