{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Your company has just constructed a new skyscraper, but you just noticed a terrible problem: there is only space to put one game room on each floor! The game rooms have not\nbeen furnished yet, so you can still decide which ones should be for table tennis and which ones should be for pool. There must be at least one game room of each type in the building.\n\nLuckily, you know who will work where in this building (everyone has picked out offices). You know that there will be $T_i$ table tennis players and $P_i$ pool players on each floor.\nOur goal is to minimize the sum of distances for each employee to their nearest game room. The distance is the difference in floor numbers: $0$ if an employee is on the same floor\nas a game room of their desired type, $1$ if the nearest game room of the desired type is exactly one floor above or below the employee, and so on."}},{"title":"Input","value":{"format":"MD","content":"The first line of the input gives the number of test cases, $T$($1\\leq T\\leq 100$). $T$ test cases follow. Each test case begins with one line with an integer $N$($2\\leq N\\leq 4000$),\nthe number of floors in the building. $N$ lines follow, each consists of $2$ integers, $T_i$ and $P_i$($1\\leq T_i, P_i\\leq 10^9$), the number of table tennis and pool players on\nthe $i$ - th floor. The lines are given in increasing order of floor number, starting with floor $1$ and going upward."}},{"title":"Output","value":{"format":"MD","content":"For each test case, output one line containing `Case #x: y`, where $x$ is the test case number (starting from $1$) and $y$ is the minimal sum of distances."}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n10 5\n4 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 9\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"In the first case, you can build a table tennis game room on the first floor and a pool game room on the second floor. In this case, the $5$ pool players on the first floor will need\nto go one floor up, and the $4$ table tennis players on the second floor will need to go one floor down. So the total distance is $9$."}}]}