---{"category_name":"easy","problem_code":"FATHUT","problem_name":"Fat Hut","problemComponents":{"constraints":"- $1 \\le T \\le 100$\n- $1 \\le N \\le 10^5$\n- $1 \\le C_i \\le 10^9$ for each valid $i$\n- $1 \\le L_i \\le A_i \\le R_i \\le 10^9$ for each valid $i$\n- The sum of $N$ over all test cases does not exceed $10^5$\n- The initial $A_i$-s are pairwise distinct\n- The initial $C_i$-s are pairwise distinct","constraintsState":true,"subtasks":"**Subtask 1 (5 points):**\n- $1 \\le N \\le 10^3$\n- $L_i = 1$ for each valid $i$\n- $R_i = 10^9$ for each valid $i$\n- $1 \\lt A_i \\lt 10^9$ for each valid $i$\n\n**Subtask 2 (10 points):**\n- $L_i = 1$ for each valid $i$\n- $R_i = 10^9$ for each valid $i$\n- $1 \\lt A_i \\lt 10^9$ for each valid $i$\n\n**Subtask 3 (10 points):**\n- $1 \\le N \\le 10^3$\n- $R_i = 10^9$ for each valid $i$\n- $A_i \\lt 10^9$ for each valid $i$\n\n**Subtask 4 (20 points):**\n- $R_i = 10^9$ for each valid $i$\n- $A_i \\lt 10^9$ for each valid $i$\n\n**Subtask 5 (20 points):**\n- $1 \\le N \\le 10^3$\n\n**Subtask 6 (35 points):**\n- Original constraints\n","subtasksState":true,"inputFormat":"- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\n- Each testcase contains $N + 1$ lines of input.\n- The first line of each test case contains a single integer $N$ - number of breakfasts.\n- $N$ lines follow. For each valid $i$, the $i^{th}$ of these lines contains four space-separated integers $A_i$, $C_i$, $L_i$, $R_i$ - current attractiveness, cost, the minimal and maximal allowed attractiveness after change of $i$-th breakfast.","inputFormatState":true,"outputFormat":"For each test case, print in a single line containing one integer - minimum number of breakfasts the Chef should change so that all the $N$ breakfasts have a chance to be taken. Print `\u0022-1\u0022`(without quotes) if it is impossible to achieve the goal.","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"2\n4\n5 1 1 5\n4 4 2 5\n2 2 2 5\n3 3 2 5\n4\n5 1 2 5\n4 4 2 5\n2 2 2 5\n3 3 2 5\n","output":"1\n2\n","explanation":"**Test case $1$**: Chef can change first breakfast\u0027s attractiveness to $1$. After that, all the $3$ breakfasts have a chance to be taken. So the answer is $1$.\n\n**Test case $2$**: Chef can change first breakfast\u0027s attractiveness to $2$ and third breakfast\u0027s attractiveness to $2.5$. There is no possible way to change the attractiveness of only one breakfast so that the condition is fulfilled. So the answer is $2$.","isDeleted":false},"1":{"id":2,"input":"1\n4\n1 1 1 1\n2 2 2 2\n3 3 3 3\n4 4 4 4\n","output":0,"explanation":"**Test case $1$**: Everything is fine already, so Chef has no need to change anything, and the answer is $0$.","isDeleted":false}}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"perucmpamypa","problem_tester":"","date_added":"2-08-2021","tags":{"0":"aug21","1":"aug21","2":"easy","3":"easy","4":"longest","5":"longest","6":"perucmpamypa"},"problem_difficulty_level":"Unavailable","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/FATHUT","time":{"view_start_date":1629117000,"submit_start_date":1629117000,"visible_start_date":1629117000,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=FATHUT","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Bengali](https://www.codechef.com/download/translated/AUG21/bengali/FATHUT.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/AUG21/mandarin/FATHUT.pdf), [Russian](https://www.codechef.com/download/translated/AUG21/russian/FATHUT.pdf), and [Vietnamese](https://www.codechef.com/download/translated/AUG21/vietnamese/FATHUT.pdf) as well.There are $N$ breakfasts in the restaurant `“Fat Hut”` where the Chef works. The $i^{th}$ breakfast has an attractiveness $A_i$ and cost $C_i$.The Chef has noticed that nobody takes the $j^{th}$ breakfast if there exists at least one breakfast $i$ such that $A_i \ge A_j$ and $C_i \lt C_j$.In other words, if a breakfast is less attractive and more expensive than any of the other dishes, then nobody is interested in that breakfast.The Chef will be happy if all the $N$ breakfasts have a chance to be taken. Unfortunately, the Chef has no power over prices. On the other hand, he can change the attractiveness of some breakfasts by some real number. However, after the changes, the attractiveness of the $i^{th}$ breakfast must lie in the interval $[L_i,R_i]$.He would also like to change the attractiveness of the minimum number of breakfasts. Help the Chef do it.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>