Nghịch lý điểm trung bình - bản khó (Paradox With Averages (Hard))

Nguồn: Kattis - averageshard

Phiên bản: Phước Hưng OJ Extended

Đề bài

Hai khoa Khoa học máy tính và Kinh tế có các sinh viên với chỉ số IQ đã biết. Hãy đếm số sinh viên của khoa Khoa học máy tính mà nếu chuyển đúng sinh viên đó sang khoa Kinh tế thì điểm trung bình IQ của cả hai khoa đều tăng.

Input

Dòng đầu chứa hai số nguyên $n_c,n_e$. Dòng thứ hai chứa $n_c$ chỉ số IQ của khoa Khoa học máy tính. Dòng thứ ba chứa $n_e$ chỉ số IQ của khoa Kinh tế.

Mỗi file input của Phước Hưng OJ chứa đúng một test case.

Output

In số sinh viên thỏa yêu cầu.

Subtask

• Subtask 1 (20%): $2\le n_c\le 50$, $1\le n_e\le 50$, $1\le IQ\le 1000$.
• Subtask 2 (30%): $2\le n_c\le 10000$, $1\le n_e\le 10000$, $1\le IQ\le 1000000$.
• Subtask 3 (50%): $2\le n_c\le 200000$, $1\le n_e\le 200000$, $1\le IQ\le 1000000000$.

Ví dụ

Input

4 3
100 90 80 70
60 65 75

Output

2

Giải thích

Trung bình ban đầu của khoa Khoa học máy tính là

còn trung bình của khoa Kinh tế là

Sinh viên có IQ $80$ thỏa điều kiện: sau khi chuyển, trung bình hai khoa lần lượt là $260/3\approx86.667$ và $280/4=70$, đều tăng. Sinh viên có IQ $70$ cũng thỏa: hai trung bình mới là $270/3=90$ và $270/4=67.5$, đều lớn hơn trước.

Sinh viên có IQ $90$ hoặc $100$ không làm trung bình khoa Khoa học máy tính tăng sau khi rời đi. Do đó có đúng $2$ sinh viên hợp lệ.