Problem F
Item Selection
You are browsing a website that lists items for sale. The website has a paging UI that displays a fixed number of items per page, one page at a time.
For example, if there are $55$ items and the page displays exactly $20$ at a time, then there are $3$ pages in total. Items $1$ through $20$ are on page $1$, items $21$ through $40$ are on page $2$, and items $41$ through $55$ are on page $3$.
You may navigate and select items using these UI elements:
-
A checkbox for every item on the current page. After you click a checkbox, a selected item becomes unselected, and an unselected item becomes selected. You cannot click a checkbox for an item that is not on the current page.
-
A “Select All” button. All unselected items on the current page become selected after you click this button.
-
A “Deselect All” button. All selected items on the current page become unselected after you click this button.
-
A “Next Page” button. Clicking it navigates to the next page and increments the current page number by one. This button is disabled on the last page.
-
A “Previous Page” button. Clicking it navigates to the previous page and decrements the current page number by one. This button is disabled on the first page.
The website has pre-selected some items for you based on its machine learning recommendation algorithm. The recommendation may or may not work for you. You know exactly the items that you want to purchase, which may differ from the pre-selected items. What is the minimum number of checkbox and button clicks required to select exactly the items you actually want?
Input
The first line of input has five integers $n, m$ ($1 \leq m \leq n \leq 10^3$), $s$ ($1 \leq s \leq \lceil \frac{n}{m} \rceil $), $p, q$ ($0 \leq p, q \leq n$), where:
-
$n$ is the number of items. The items have item numbers from $1$ to $n$.
-
$m$ is the fixed number of items displayed per page.
-
$s$ is the number of the page currently displayed.
-
$p$ is the number of preselected items.
-
$q$ is the number of items you want.
Each of the next $p$ lines contains an integer $i$ ($1 \le i \le n$). These are the item numbers of the preselected items. These $p$ items are distinct and are listed in increasing order. It is possible that the website has pre-selected none of the items ($p = 0$), in which case the input has no lines for pre-selected items.
Each of the next $q$ lines contains an integer $j$ ($1 \le j \le n$). These are the item numbers of the items you want to buy. These $q$ items are distinct and are listed in increasing order. It is possible that you want to buy none of the items ($q = 0$), in which case the input has no lines for items you want.
Output
Output a single integer, which is the minimum number of checkbox and button clicks required to select exactly the items you want.
Sample Input 1 | Sample Output 1 |
---|---|
11 4 1 5 5 1 4 9 10 11 1 3 6 7 8 |
7 |