{"extraResources":{"example.01.mu":"TVXzATINCiFjMTs0IDIgNg0KMSAxDQoxIDINCjEgNg0KMiAzDQohYzI7MiA0IDUNCjMgNA0KMiA0DQo="},"scoring":null,"notes":"","legend":"\\textit{Préférence} is a card game which is very popular in Eastern Europe. It is usually played with a 32-card deck, which consists of pip cards from 7 to 10, Jack, Queen, King, and Ace in each of the four suits: Spades, Clubs, Diamonds, and Hearts. In each round of the game, three players receive ten cards each, and two cards are left on the table as a talon. Then, a phase of auction happens, where players make their bids, which are obligations to take at least a certain number of tricks. A special case of a bid is a so-called \\textit{misère}, which is an obligation to take no tricks regardless of other players' moves.\r\n\r\nIn this task, we will consider a special modification of préférence which is played with a modified deck containing $A\\cdot B$ cards, where $A$ is a number of suits, and $B$ is the number of ranks in each suit. For example, the standard 32-card deck for the préférence game has $A = 4$ suits and $B = 8$ ranks. For convenience, we'll number the suits from $1$ to $A$, and the ranks from $1$ to $B$.\r\n\r\nYou need to solve a puzzle about this modification of préférence. In this modification, we'll say that a misère is \\textit{guaranteed} if for every suit, after we order the cards belonging to this suit in your hand by their rank as $b_1 < b_2 < \\cdots < b_k$ (where $k$ is the number of cards of the suit in your hand), the following condition is satisfied: $b_i \\le 2i - 1$ for all $i$ from $1$ to $k$. If you don't have any cards of the suit ($k = 0$), the condition is trivially satisfied.\r\n\r\nYou have $n$ cards in your hand, and you will be allowed to choose any $x$ cards you don't have and add them to your hand. Then, you must select any $x$ of your $n + x$ cards and drop them, leaving some $n$ cards in your hand. Your task is to find the smallest possible $x$ such that you can transform your hand to a guaranteed misère.","authorLogin":"tourist","language":"english","timeLimit":2000,"output":"For each test case, print the smallest non-negative integer value of $x$ such that you can transform your hand to a guaranteed misère by first adding $x$ cards that you don't have to your hand, and then dropping any $x$ cards from your hand.\r\n\r\nIt can be shown that such a value of $x$ always exists.","inputFile":"stdin","outputFile":"stdout","input":"Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \\le t \\le 1000$). The description of the test cases follows.\r\n\r\nThe first line of each test case contains three integers $n$, $A$, and $B$, denoting the number of cards in your hand, the number of suits in the deck, and the number of ranks in the deck ($1 \\le n \\le 5000$; $1\\le A, B\\le 10^9$).\r\n\r\nThe $i$-th of the following $n$ lines contains two integers $a_i$ and $b_i$ and describes one card, where $a_i$ is the suit of the $i$-th card, and $b_i$ is its rank ($1 \\le a_i \\le A$; $1 \\le b_i \\le B$). All the cards in your hand are distinct.\r\n\r\nIt is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"1\r\n2\r\n","input":"2\r\n4 2 6\r\n1 1\r\n1 2\r\n1 6\r\n2 3\r\n2 4 5\r\n3 4\r\n2 4\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Misère","interaction":null,"memoryLimit":1073741824,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Андрей Лопатин, Геннадий Короткевич\\\\\r\n         Разработка: & Андрей Лопатин\\\\\r\n     \\end{tabular}\r\n}\r\n\r\nВ каждой масти, если мы скидываем $t$ карт, $0 \\le t \\le k$, мы можем посчитать, сколько карт нам нужно будет добрать, чтобы эта масть стала требуемого вида (естественно, что мы скидываем самые большие карты, а добираем --- самые маленькие).\r\n\r\nПрименим метод динамического программирования: обозначим за $f(i, j)$ минимальное число карт, которое нужно будет добрать, если среди первых $i$ мастей мы скинем $j$ карт в сумме.\r\n\r\nДля того, чтобы пересчитывать функцию, в очередной масти перебираем параметр $t$ --- количество скидываемых карт. Естественным образом рассматриваем только те масти, которые присутствуют у нас на руках, остальные пропускаются и не участвуют в решении (можно рассматривать это, как сжатие координат).\r\n\r\nСостояний $O(n^2)$, и суммарное число переходов тоже оценивается как $O(n^2)$~--- а точнее, число переходов равно $n$, умноженному на сумму количеств вариантов $t$ (которое, в свою очередь, равно $k+1$ для масти размера $k$).\r\n\r\nОтветом на задачу является минимальное такое $j$, для которого $f(m, j) \\le j$ (где $m$ --- максимальная масть)."}