solution

Cho $X \sim \text{Binomial}(n, p)$ với xác suất thành công $p = a/b$ (không nhất thiết là phân số tối giản trong dữ liệu vào, $0 \le a \le b$, $b \ge 1$). Cho một ngưỡng $\alpha = c/d$ ($0 \le c \le d$, $d \ge 1$).

Hãy tìm số nguyên nhỏ nhất $k$ với $0 \le k \le n$ sao cho $P(X \ge k) = \sum_{i=k}^{n} \binom{n}{i} p^i (1-p)^{n-i} \le \alpha.$

Vì $p$ và $\alpha$ đều là số hữu tỉ, $P(X \ge k)$ cũng là một số hữu tỉ; việc so sánh với $\alpha$ phải được thực hiện bằng số học phân số chính xác (không dùng số thực dấu phẩy động) để tránh sai số làm tròn. Nếu không tồn tại $k$ nào trong đoạn $[0,n]$ thỏa mãn, in ra $-1$.

Ví dụ: $n=5$, $p=1/2$, $\alpha=1/2$. Ta có $P(X\ge 3) = 16/32 = 1/2 \le 1/2$ trong khi $P(X\ge 2) = 26/32 > 1/2$, nên $k=3$ là câu trả lời nhỏ nhất thỏa mãn.

Input:

5 1 2 1 2

Output:

3