title: [USACO16DEC] Moocast G

description:
Farmer John's $N$ cows ($1 \leq N \leq 1000$) want to organize an emergency "moo-cast" system for broadcasting important messages among themselves.

Instead of mooing at each-other over long distances, the cows decide to equip themselves with walkie-talkies, one for each cow. These walkie-talkies each have a limited transmission radius, but cows can relay messages to one-another along a path consisting of several hops, so it is not necessary for every cow to be able to transmit directly to every other cow.

The cows need to decide how much money to spend on their walkie-talkies. If they spend $X$, they will each get a walkie-talkie capable of transmitting up to a distance of $\sqrt{X}$. That is, the squared distance between two cows must be at most $X$ for them to be able to communicate.

Please help the cows determine the minimum integer value of $X$ such that a broadcast from any cow will ultimately be able to reach every other cow.

inputFormat:
The first line of input contains $N$.

The next $N$ lines each contain the $x$ and $y$ coordinates of a single cow. These are both integers in the range $0 \ldots 25,000$.

outputFormat: Write a single line of output containing the integer $X$ giving the minimum amount the cows must spend on walkie-talkies.

translation:
Farmer John 的 $N$ 头牛 ($1 \leq N \leq 1000$) 为了在他们之间传播信息，想要组织一个"哞哞广播"系统。奶牛们决定去用步话机装备自己而不是在很远的距离之外互相哞哞叫，所以每一头奶牛都必须有一个步话机。这些步话机都有一个限制传播半径，但是奶牛们可以间接地通过中间奶牛传播信息，所以并不是每头牛都必须直接向其他每一头奶牛连边。

奶牛们需要去决定多少钱花在步话机上，如果他们花了 $X$, 那么他们都将会得到 $\sqrt{X}$ 距离的步话机。所以，两头牛之间的欧几里得距离平方最多是 $X$。请帮助奶牛们找到最小的 $X$ 使得图是强连通的。

hint: 感谢@MrMorning 提供翻译


title: 等式

type: P

background: ZKC 有一天突发奇想，望着天空想出一道很好的问题，但是绞尽脑汁又不会做，所以请你来帮他解决。

description: 给出 $a,b,c,x_1,x_2,y_1,y_2$，求满足 $ax+by+c=0$，且 $x\in [x_1,x_2]$，$y\in [y_1,y_2]$ 的整数解有多少对。

inputFormat: 一行七个整数 $a,b,c,x_1,x_2,y_1,y_2$，整数间用空格隔开。

outputFormat: 输出整数解有多少对。


title: [USACO16DEC] Cow Checklist G

description:
Every day, Farmer John walks through his pasture to check on the well-being ofeach of his cows.   On his farm he has two breeds of cows, Holsteins andGuernseys.  His $H$ Holsteins are conveniently numbered $1 \ldots H$, and his$G$ Guernseys are conveniently numbered $1 \ldots G$($1 \leq H \leq 1000, 1 \leq G \leq 1000$).  Each cow is located at a point inthe 2D plane (not necessarily distinct).

每天，农夫约翰走过他的牧场，检查他的每头奶牛的存在感。在他的农场，他有两个品种的牛，Holsteins和Guernseys。他的H Holsteins方便地编号为$1 \ldots H$，并且他的G Guernseys方便地编号为$1 \ldots G$($1 \leq H \leq 1000, 1 \leq G \leq 1000$)。每个牛位于2D平面中的点（不一定是不同的）。

Farmer John starts his tour at Holstein 1, and ends at Holstein $H$.  He wantsto visit each cow along the way, and for convenience in maintaining hischecklist of cows visited so far, he wants to visit the Holsteins and Guernseysin the order in which they are numbered.  In the sequence of all $H+G$ cows hevisits, the Holsteins numbered $1 \ldots H$ should appear as a (not necessarilycontiguous) subsequence, and likewise for the Guernseys. Otherwise stated, thesequence of all $H+G$ cows should be formed by  interleaving the list ofHolsteins numbered $1 \ldots H$ with the list of Guernseys numbered$1 \ldots G$.

农夫约翰从Holsteins 1出发，在Holsteins H结束。他想要沿途参观每头牛，为了方便保持他到目前为止访问的牛的清单，他想按他们的编号顺序访问Holsteins和Guernseys。在他访问的所有$H+G$头牛的序列中，Holsteins编号为$1 \ldots H$应该显示为（不一定是连续的）子序列，对于Guernseys也相同。换句话说，所有$H+G$牛的序列应该通过将编号为$1 \ldots H$的Holsteins列表与编号为$1 \ldots G$的Guernseys列表交错形成。

When FJ moves from one cow to another cow traveling a distance of $D$, heexpends $D^2$ energy.  Please help him determine the minimum amount of energyrequired to visit all his cows according to a tour as described above.

当FJ从一头母牛移动到另一头母牛，行进距离为$D$时，他消耗$D^2$能量。请帮助他确定访问所有奶牛所需的最低能量。

inputFormat:
The first line of input contains $H$ and $G$, separated by a space.

The next $H$ lines contain the $x$ and $y$ coordinates of the $H$ Holsteins, and the next $G$ lines after that contain coordinates of the Guernseys.  Each

coordinate is an integer in the range $0 \ldots 1000$.

outputFormat: Write a single line of output, giving the minimum energy required for FJ's tour of all the cows.


title: [USACO06DEC] Wormholes G

background: [英文题面见此链接](https://www.luogu.com.cn/paste/mxuf6zpl)

description:
John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。

John 的每个农场有 $m$ 条小路（无向边）连接着 $n$ 块地（从 $1 \sim n$ 标号），并有 $w$ 个虫洞。

现在 John 希望能够从某块地出发，走过一条路径回到出发点，且同时也回到了出发时刻以前的某一时刻。请你告诉他能否做到。

inputFormat:
输入的第一行是一个整数 $T$，代表测试数据的组数。

每组测试数据的格式如下：

每组数据的第一行是三个用空格隔开的整数，分别代表农田的个数 $n$，小路的条数 $m$，以及虫洞的个数 $w$。

每组数据的第 $2$ 到第 $(m + 1)$ 行，每行有三个用空格隔开的整数 $u, v, p$，代表有一条连接 $u$ 与 $v$ 的小路，经过这条路需要花费 $p$ 的时间。

每组数据的第 $(m + 2)$ 到第 $(m + w + 1)$ 行，每行三个用空格隔开的整数 $u, v, p$，代表点 $u$ 存在一个虫洞，经过这个虫洞会到达点 $v$，并回到 $p$ 秒之前。

outputFormat: 对于每组测试数据，输出一行一个字符串，如果能回到出发时刻之前，则输出 `YES`，否则输出 `NO`。

hint:
#### 样例 2 解释

John 只需要沿着 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ 的路径一直转圈即可，每转完一圈，时间就会减少一秒。

#### 数据范围与约定

对于 $100\%$ 的数据，$1 \le T \le 5$，$1 \le n \le 500$，$1 \le m \le 2500$，$1 \le w \le 200$，$1 \le p \le 10^4$。


title: [USACO06DEC] The Fewest Coins G

description:
Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number is.

FJ wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, ..., VN (1 ≤ Vi ≤ 120). Farmer John is carrying C1 coins of value V1, C2 coins of value V2, ...., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner (although Farmer John must be sure to pay in a way that makes it possible to make the correct change).

农夫 John 想到镇上买些补给。为了高效地完成任务，他想使硬币的转手次数最少。即使他交付的硬 币数与找零得到的的硬币数最少。

John 想要买价值为 $T$ 的东西。有 $N$（$1 \le N \le 100$）种货币参与流通，面值分别为 $V_1,V_2,\dots,V_N$（$1 \le V_i \le 120$）。John 有 $C_i$ 个面值为 $V_i$ 的硬币（$0 \le C_i \le 10 ^ 4$）。

我们假设店主有无限多的硬币， 并总按最优方案找零。**注意**无解输出 `-1`。

inputFormat:
Line 1: Two space-separated integers: N and T.

Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1, ...VN)

Line 3: N space-separated integers, respectively C1, C2, ..., CN

outputFormat: Line 1: A line containing a single integer, the minimum number of coins involved in a payment and change-making. If it is impossible for Farmer John to pay and receive exact change, output -1.

hint: Farmer John pays 75 cents using a 50 cents and a 25 cents coin, and receives a 5 cents coin in change, for a total of 3 coins used in the transaction.


title: [USACO06DEC] Milk Patterns G

description:
Farmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigation, he discovered that although he can't predict the quality of milk from one day to the next, there are some regular patterns in the daily milk quality.

To perform a rigorous study, he has invented a complex classification scheme by which each milk sample is recorded as an integer between 0 and 1,000,000 inclusive, and has recorded data from a single cow over N (1 ≤ N ≤ 20,000) days. He wishes to find the longest pattern of samples which repeats identically at least K (2 ≤ K ≤ N) times. This may include overlapping patterns -- 1 2 3 2 3 2 3 1 repeats 2 3 2 3 twice, for example.

Help Farmer John by finding the longest repeating subsequence in the sequence of samples. It is guaranteed that at least one subsequence is repeated at least K times.

inputFormat:
Line 1: Two space-separated integers: N and K

Lines 2..N+1: N integers, one per line, the quality of the milk on day i appears on the ith line.

outputFormat: Line 1: One integer, the length of the longest pattern which occurs at least K times

translation: 农夫 John 发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John 的牛奶按质量可以被赋予一个 $0$ 到 $1000000$ 之间的数。并且 John 记录了 $N$（$1 \le N \le 2 \times 10 ^ 4$）天的牛奶质量值。他想知道最长的出现了至少 $K$（$2 \le K \le N$）次的模式的长度。比如 `1 2 3 2 3 2 3 1` 中 `2 3 2 3` 出现了两次。当 $K = 2$ 时，这个长度为 $4$。


title: [USACO06DEC] Cow Picnic S

description:
The cows are having a picnic! Each of Farmer John's K (1 ≤ K ≤ 100) cows is grazing in one of N (1 ≤ N ≤ 1,000) pastures, conveniently numbered 1...N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths (no path connects a pasture to itself).

The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

$K(1 \le K \le 100)$ 只奶牛分散在 $N(1 \le N \le 1000)$ 个牧场．现在她们要集中起来进餐。牧场之间有 $M(1 \le M \le 10000)$ 条有向路连接，而且不存在起点和终点相同的有向路．她们进餐的地点必须是所有奶牛都可到达的地方。那么，有多少这样的牧场可供进食呢？

inputFormat:
Line 1: Three space-separated integers, respectively: K, N, and M

Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the number of the pasture in which cow i is grazing.

Lines K+2..M+K+1: Each line contains two space-separated integers, respectively A and B (both 1..N and A != B), representing a one-way path from pasture A to pasture B.

outputFormat: Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.

hint: The cows can meet in pastures 3 or 4.


title: [USACO06DEC] Cow Roller Coaster S

description:
The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget.

The roller coaster will be built on a long linear stretch of land of length L (1 ≤ L ≤ 1,000). The roller coaster comprises a collection of some of the N (1 ≤ N ≤ 10,000) different interchangable components. Each component i has a fixed length Wi (1 ≤ Wi ≤ L). Due to varying terrain, each component i can be only built starting at location Xi (0 ≤ Xi ≤ L - Wi). The cows want to string together various roller coaster components starting at 0 and ending at L so that the end of each component (except the last) is the start of the next component.

Each component i has a "fun rating" Fi (1 ≤ Fi ≤ 1,000,000) and a cost Ci (1 ≤ Ci ≤ 1000). The total fun of the roller coster is the sum of the fun from each component used; the total cost is likewise the sum of the costs of each component used. The cows' total budget is B (1 ≤ B ≤ 1000). Help the cows determine the most fun roller coaster that they can build with their budget.

inputFormat:
Line 1: Three space-separated integers: L, N and B.

Lines 2..N+1: Line i+1 contains four space-separated integers, respectively: Xi, Wi, Fi, and Ci.

outputFormat: Line 1: A single integer that is the maximum fun value that a roller-coaster can have while staying within the budget and meeting all the other constraints. If it is not possible to build a roller-coaster within budget, output -1.

translation:
**【题目描述】**

有 $n$ 条线段，每条线段只能放在数轴上的一个特定位置，并且第 $i$ 根线段有如下几个属性：$X_i$（该线段放在数轴上的起点），$W_i$（该线段长度），$F_i$（你若使用该线段你能获得的价值），$C_i$（你若使用该线段你所需要的费用）。现在让你从中选出一些线段，使得这些线段能够铺满数轴上的区间 $[0,L]$ 且线段必须首尾相接（也就是不能重叠，也不能空缺），并且所花费用和不超过 $B$，同时要使你收获的价值尽量大，请你找到这个方案。

**【输入格式】**

第一行三个整数 $L, n, B$。

接下来 $n$ 行，每行四个整数 $X_i, W_i, F_i, C_i$ 表示第 $i$ 根线段的四个属性。

**【输出格式】**

一个整数，表示你能获得的最大价值和。若无法满足上述要求，则输出 $-1$。

hint: Taking the 3rd, 5th and 6th components gives a connected roller-coaster with fun value 17 and cost 7. Taking the first two components would give a more fun roller-coaster (25) but would be over budget.


title: [USACO06DEC] River Hopscotch S

description:
Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤ N ≤ 50,000) more rocks appear, each at an integral distance Di from the start (0 < Di < L).

To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.

Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 ≤ M ≤ N).

FJ wants to know exactly how much he can increase the shortest distance \*before\* he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.

奶牛跳房子：从N块石头中移除M块，使得间距最小值最大。

inputFormat:
Line 1: Three space-separated integers: L, N, and M

Lines 2..N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position.

outputFormat: Line 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks

hint: Before removing any rocks, the shortest jump was a jump of 2 from 0 (the start) to 2. After removing the rocks at 2 and 14, the shortest required jump is a jump of 4 (from 17 to 21 or from 21 to 25).


title: [USACO06FEB] Cellphones G

description:
The cows have started using cellphones to cowmunicate with each other, but have found that the button layout doesn't suit their hooves very well. They are designing a special cellphone with fewer but larger buttons.

One feature they liked on the standard cellphones was predictive text. Each button has a few letters associated with it, and one types a word by pushing the associated buttons. Because there is more than one letter for each button, this can be ambiguous for some words.  However, most of the time the ambiguity can be resolved by using a dictionary to determine what word the user wanted.

Since the cows are designing a custom cellphone, they are also going to replace the English alphabet with the Cow alphabet. By an amazing coincidence, the cow alphabet is simply the first L (1 <= L <= 26) letters of the English alphabet, in the same order. They want to find out how to assign the letters of the Cow alphabet to the B buttons (1 <= B <= L) in such a way that the maximum number of words in their dictionary are unambiguous when entered with predictive text. Like normal cellphones, they want the letters on each button to be a contiguous section (one or more consecutive letters) of the alphabet.

奶牛的名字都是由英文字母表的前1(1 < K 26)个字母构成的.现在想设计一种手机， 有个按键.请你把这L个字母按顺序分配给B个按键，使能够通过按这些键而唯一确 定的奶牛数尽量多.

inputFormat:
Line 1: Two space-separated integers: B and L

Line 2: D, the number of words in the dictionary (1 <= D <= 1000)

Lines 3..D+2: Each line contains one word from the dictionary in upper case and of length 1..10 characters. The words are presented in alphabetical order and with no duplicates.

outputFormat:
Line 1: The number of words in the Cow dictionary that have unique button sequences.

Lines 2..B+1: The nth line contains the letters that appear on button n, in upper case and alphabetical order. The lines must be listed in alphabetical order, and every Cow letter must appear exactly once. If there is more than one optimal solution, use the one that places the most letters on button 1. Ties are broken by placing the most letters on button 2, etc.

samples:
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK

hint:
Explanation of the sample:

Button 1 contains AB, button two contains C-K, and button 3 contains LM. The words CELL, DILL, FILL and FILM are all entered as 2233, while the remaining 7 words are all entered uniquely.


title: [USACO06FEB] Steady Cow Assignment G

description:
Farmer John's N (1 <= N <= 1000) cows each reside in one of B (1 <= B <= 20) barns which, of course, have limited capacity. Some cows really like their current barn, and some are not so happy.

FJ would like to rearrange the cows such that the cows are as equally happy as possible, even if that means all the cows hate their assigned barn.

Each cow gives FJ the order in which she prefers the barns.  A cow's happiness with a particular assignment is her ranking of her barn. Your job is to find an assignment of cows to barns such that no barn's capacity is exceeded and the size of the range (i.e., one more than the positive difference between the the highest-ranked barn chosen and that lowest-ranked barn chosen) of barn rankings the cows give their assigned barns is as small as possible.

inputFormat:
Line 1: Two space-separated integers, N and B

Lines 2..N+1: Each line contains B space-separated integers which are exactly 1..B sorted into some order. The first integer on line i+1 is the number of the cow i's top-choice barn, the second integer on that line is the number of the i'th cow's second-choice barn, and so on.

Line N+2: B space-separated integers, respectively the capacity of the first barn, then the capacity of the second, and so on. The sum of these numbers is guaranteed to be at least N.

outputFormat: Line 1: One integer, the size of the minumum range of barn rankings the cows give their assigned barns, including the endpoints.

translation: 有 $N$ 头牛，$B$ 个牛棚。告诉你每头牛心里牛棚的座次，即哪个牛棚他最喜欢，哪个第 $2$ 喜欢，哪个第 $3$ 喜欢，等等。但牛棚容量一定，所以每头牛分配到的牛棚在该牛心中的座次有高有低。现在求一种最公平的方法分配牛到牛棚，使所有牛中，所居牛棚的座次最高与最低的跨度最小。

hint:
Explanation of the sample:

Each cow can be assigned to her first or second choice: barn 1 gets cows 1 and 5, barn 2 gets cow 2, barn 3 gets cow 4, and barn 4 gets cows 3 and 6.


title: [USACO06FEB] Treats for the Cows G/S

description:
FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time.

The treats are interesting for many reasons:The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats.Like fine wines and delicious cheeses, the treats improve with age and command greater prices.The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000).Cows pay more for treats that have aged longer: a cow will pay v(i)\*a for a treat of age a.Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally?

The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

约翰经常给产奶量高的奶牛发特殊津贴，于是很快奶牛们拥有了大笔不知该怎么花的钱。为此，约翰购置了 $N$（$1 \leq N \leq 2000$） 份美味的零食来卖给奶牛们。每天约翰售出一份零食。当然约翰希望这些零食全部售出后能得到最大的收益，这些零食有以下这些有趣的特性：
+ 零食按照 $1, \ldots, N$ 编号，它们被排成一列放在一个很长的盒子里。盒子的两端都有开口，约翰每天可以从盒子的任一端取出最外面的一个。
+ 与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃。当然，这样约翰就可以把它们卖出更高的价钱。
+ 每份零食的初始价值不一定相同。约翰进货时，第i份零食的初始价值为 $V_i$（$1 \leq V \leq 1000$）。
+ 第i份零食如果在被买进后的第 $a$ 天出售，则它的售价是 $V_i \times a$。

$V_i$ 的是从盒子顶端往下的第i份零食的初始价值。约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱。

inputFormat:
Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains the value of treat v(i)

outputFormat: Line 1: The maximum revenue FJ can achieve by selling the treats

hint:
Explanation of the sample:

Five treats. On the first day FJ can sell either treat #1 (value 1) or treat #5 (value 2).

FJ sells the treats (values 1, 3, 1, 5, 2) in the following order of indices: 1, 5, 2, 3, 4, making 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.


title: [USACO06FEB] Stall Reservations S

description:
Oh those picky $N$ ($1 \leq N \leq 50,000$) cows! They are so picky that each one will only be milked over some precise time interval $A..B$ ($1 \leq A \leq B \leq 1,000,000$), which includes both times $A$ and $B$. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.

Help FJ by determining: The minimum number of stalls required in the barn so that each cow can have her private milking period. An assignment of cows to these stalls over time. Many answers are correct for each test dataset; a program will grade your answer.

约翰的 $N$（$1\leq N\leq 50000$）头奶牛实在是太难伺候了，她们甚至有自己独特的产奶时段。对于某一头奶牛，她每天的产奶时段是固定的时间段 $[A,B]$（即 $A$ 到 $B$，包括 $A$ 和 $B$）。这使得约翰必须开发一个调控系统来决定每头奶牛应该被安排到哪个牛棚去挤奶，因为奶牛们并不希望在挤奶时被其它奶牛看见。

请帮约翰计算：如果要满足奶牛们的要求，并且每天每头奶牛都要被挤过奶，至少需要多少牛棚和每头牛应该在哪个牛棚被挤奶。如果有多种答案，输出任意一种均可。

inputFormat:
Line $1$: A single integer, $N$

Lines $2..N+1$: Line $i+1$ describes cow $i$'s milking interval with two space-separated integers.

第 $1$ 行为一个整数 $N$。

第 $2\sim (N+1)$ 行，每行两个数字，第 $(i+1)$ 行的数字代表第 $i$ 头奶牛的产奶时段。

outputFormat:
Line $1$: The minimum number of stalls the barn must have.

Lines $2..N+1$: Line $i+1$ describes the stall to which cow i will be assigned for her milking period.

第 $1$ 行输出一个整数，代表需要牛棚的最少数量。

第 $2\sim (N+1)$ 行，每行一个数字，第 $(i+1)$ 行的数字代表第 $i$ 头奶牛将会被安排到哪个牛棚挤奶。

hint:
Explanation of the sample:

Here's a graphical schedule for this output:

Time     1  2  3  4  5  6  7  8  9 10

Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>

Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..

Stall 3 .. .. c3>>>>>>>>> .. .. .. ..

Stall 4 .. .. .. c5>>>>>>>>> .. .. ..Other outputs using the same number of stalls are possible.

由@FlierKing提供spj


title: [USACO06JAN] Redundant Paths G

description:
In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples.  The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another.

Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way.

There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.

inputFormat:
Line 1: Two space-separated integers: F and R

Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.

outputFormat: Line 1: A single integer that is the number of new paths that must be built.

translation:
为了从 $F(1 \le F \le 5000)$ 个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。

每对草场之间已经有至少一条路径．给出所有 $R\ (F-1 \le R \le 10000)$ 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场．对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。

hint:
Explanation of the sample:

One visualization of the paths is:

![](https://cdn.luogu.com.cn/upload/image_hosting/cubnel5k.png)

Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions.

![](https://cdn.luogu.com.cn/upload/image_hosting/rgguiytp.png)

Check some of the routes:

- 1 – 2:  1 –> 2 and 1 –> 6 –> 5 –> 2
- 1 – 4:  1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4
- 3 – 7:  3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7

Every pair of fields is, in fact, connected by two routes.

It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.


title: [USACO06JAN] Roping the Field G

description:
Farmer John is quite the nature artist: he often constructs large works of art on his farm. Today, FJ wants to construct a giant "field web". FJ's field is large convex polygon with fences along the boundary and fence posts at each of the N corners (1 <= N <= 150). To construct his field web, FJ wants to run as many ropes as possible in straight lines between pairs of non-adjacent fence posts such that no two ropes cross.

There is one complication: FJ's field is not completely usable. Some evil aliens have created a total of G (0 <= G <= 100) grain circles in the field, all of radius R (1 <= R <= 100,000). FJ is afraid to upset the aliens, and therefore doesn't want the ropes to pass through, or even touch the very edge of a grain circle. Note that although the centers of all the circles are contained within the field, a wide radius may make it extend outside of the field, and both fences and fence posts may be within a grain circle.

Given the locations of the fence posts and the centers of the circles, determine the maximum number of ropes that FJ can use to create his field web.

FJ's fence pots and the circle centers all have integer coordinates X and Y each of which is in the range 0..1,000,000.

约翰真是一个自然派艺术大师，他常常在他的田地上创作一些巨大的艺术杰作.今天，他想 在麦田上创作一幅由绳索构成的巨画.他的麦田是一个多边形，由N(l<N< 150)个篱笆粧和之 间的篱笆围成.为了创作他的巨画，他打算用尽量多的数量的绳索，笔直地连接两个不相邻的篱 笆粧.但是为了画作的优美，任意两根绳索不得交叉.

约翰有一个难处：一些邪恶的外星人在他的麦田上整出了100)个怪圈.这些怪圈 都有一定的半径丑(1<丑< 100000).他不敢惹外星人，所以不想有任何绳索通过这些怪圈，即使 碰到怪圈的边际也不行.这些怪圈的圆心都在麦田之内，但一些怪圈可能有部分在麦田之外.一 些篱笆或者篱笆粧都有可能在某一个怪圈里.

给出篱笆粧和怪圈的坐标，计算最多的绳索数.所有的坐标都是[0，10^6]内的整数.

输入说明

第1行输入三个整数接下来N行每行输入两个整数表示篱笆粧的坐标.接下来G行每 行输入两个整数表示一个怪圈的圆心坐标.

inputFormat:
Line 1: Three space-separated integers: N, G, and R

Lines 2..N+1: Each line contains two space-separated integers that are the X,Y position of a fence post on the boundary of FJ's field.

Lines N+2..N+G+1: Each line contains two space-separated integers that are the X,Y position of a circle's center inside FJ's field.

outputFormat: Line 1: A single integer that is the largest number of ropes FJ can use for his artistic creation.

hint:
Explanation of the sample:

A pentagonal field, in which all possible ropes are blocked by three grain circles, except for the rope between fenceposts 2 and 4.


title: [USACO06JAN] Corral the Cows G

description:
Farmer John wishes to build a corral for his cows. Being finicky beasts, they demand that the corral be square and that the corral contain at least C (1 <= C <= 500) clover fields for afternoon treats. The corral's edges must be parallel to the X,Y axes.

FJ's land contains a total of N (C <= N <= 500) clover fields, each a block of size 1 x 1 and located at with its lower left corner at integer X and Y coordinates each in the range 1..10,000. Sometimes more than one clover field grows at the same location; such a field would have its location appear twice (or more) in the input. A corral surrounds a clover field if the field is entirely located inside the corral's borders.

Help FJ by telling him the side length of the smallest square containing C clover fields.

Farmer John 希望为他的奶牛们建立一个畜栏。

这些挑剔的奶牛要求畜栏必须是正方形的，而且至少要包含 $C$ 片三叶草，来当做它们的下午茶。

约翰的土地里一共包含 $N$ 片三叶草，每单位三叶草位于一个 $1\times 1$ 的土地区域内。坐标都为整数，范围在 $1$ 到 $10000$ 以内。

**多片的三叶草可能会位于同一个 $1\times 1$ 的区域内，所以在输入内，同一个区域坐标可能出现多次。**

请你帮 Farmer John 计算一下，在能包含至少 $C$ 片三叶草的情况下，畜栏的最小边长是多少。

$1\le C\le N\le 500$。

inputFormat:
Line 1: Two space-separated integers: C and N

Lines 2..N+1: Each line contains two space-separated integers that are the X,Y coordinates of a clover field.

outputFormat: Line 1: A single line with a single integer that is length of one edge of the minimum size square that contains at least C clover fields.

hint:
Explanation of the sample:

```php
|*   *
| * *
+------
```

Below is one 4x4 solution (C's show most of the corral's area); many others exist.

```php
|CCCC
|CCCC
|*CCC*
|C*C*
+------
```


title: [USACO06JAN] The Cow Prom S

description: 有一个 $n$ 个点，$m$ 条边的有向图，请求出这个图点数大于 $1$ 的强连通分量个数。

inputFormat:
第一行为两个整数 $n$ 和 $m$。

第二行至 $m+1$ 行，每一行有两个整数 $a$ 和 $b$，表示有一条从 $a$ 到 $b$ 的有向边。

outputFormat: 仅一行，表示点数大于 $1$ 的强连通分量个数。

hint:
#### 数据规模与约定

对于全部的测试点，保证 $2\le n \le 10^4$，$2\le m\le 5\times 10^4$，$1 \leq a, b \leq n$。


title: [USACO06JAN] The Grove S

description:
The pasture contains a small, contiguous grove of trees that has no 'holes' in the middle of the it.  Bessie wonders: how far is it to walk around that grove and get back to my starting position? She's just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn't think you could pass 'through' the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take.

Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 <= R <= 50, 1 <= C <= 50). Here's a typical example where '.' is pasture (which Bessie may traverse), 'X' is the grove of trees, '\*' represents Bessie's start and end position, and '+' marks one shortest path she can walk to circumnavigate the grove (i.e., the answer):

```cpp
...+...
..+X+..
.+XXX+.
..+XXX+
..+X..+
...+++*
```
The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she's starting 'outside' the grove instead of in a sort of 'harbor' that could complicate finding the best path.

牧场里有树林，林子里没有坑，贝茜很想知道，最少几步能绕树林走一圈，最后回到起点.她能上下左右走，也能走对角线格子.

牧场被分成 $R$ 行 $C$ 列 $(1\leq R\leq 50,\ 1\leq C\leq 50)$ 。下面是一张样例的地图，其中 `.` 表示贝茜可以走的空地， `X` 表示树林，表示起点.而贝茜走的最近的路已经特别地用 `+` 表示 出来.

题目**保证存在最短路径**，且森林形成一个联通块。

inputFormat:
Line 1: Two space-separated integers: R and C

Lines 2..R+1: Line i+1 describes row i with C characters (with no spaces between them).

outputFormat: Line 1: The single line contains a single integer which is the smallest number of steps required to circumnavigate the grove.


title: [USACO06NOV] Roadblocks G

description:
Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

inputFormat:
Line 1: Two space-separated integers: N and R

Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

outputFormat: Line 1: The length of the second shortest path between node 1 and node N

translation:
贝茜把家搬到了一个小农场，但她常常回到 FJ 的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。
贝茜所在的乡村有 $R(1\le R \le 10^5)$ 条双向道路，每条路都联结了所有的 $N(1\le N\le 5000)$ 个农场中的某两个。贝茜居住在农场 $1$，她的朋友们居住在农场 $N$（即贝茜每次旅行的目的地）。
贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。


title: [USACO06NOV] Bad Hair Day S

description:
农夫约翰有 $N$ 头奶牛正在过乱头发节。

每一头牛都站在同一排面朝右，它们被从左到右依次编号为 $1, 2, \cdots, N$。编号为 $i$ 的牛身高为 $h_i$。第 $N$ 头牛在最前面，而第 $1$ 头牛在最后面。

对于第 $i$ 头牛**前面**的第 $j$ 头牛，如果 $h_i>h_{i+1}, h_i>h_{i+2}, \cdots, h_i>h_j$，那么认为第 $i$ 头牛可以看到第 $i+1$ 到第 $j$ 头牛。

定义 $C_i$ 为第 $i$ 头牛所能看到的牛的数量。请帮助农夫约翰求出 $C _ 1 + C _ 2 + \cdots + C _ N$。

inputFormat:
输入共 $N + 1$ 行。

第一行为一个整数 $N$，代表牛的个数。
接下来 $N$ 行，每行一个整数 $a _ i$，分别代表第 $1, 2, \cdots, N$ 头牛的身高。

outputFormat: 输出共一行一个整数，代表 $C _ 1 + C _ 2 + \cdots + C _ N$。

hint:
### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq N \leq 8 \times 10 ^ 4$，$1 \leq h _ i \leq 10 ^ 9$。


title: [USACO06NOV] Big Square S

background: [English version](https://www.luogu.com.cn/paste/x781adew)

description: 农民 John 的牛参加了一次和农民 Bob 的牛的竞赛。他们在区域中画了一个$N\times N$ 的正方形点阵，两个农场的牛各自占据了一些点。当然不能有两头牛处于同一个点。农场的目标是用自己的牛作为$4$个顶点，形成一个面积最大的正方形 （不必须和边界平行） 。 除了 Bessie 以外，John其他的牛都已经放到点阵中去了，要确定Bessie放在哪个位置，能使得John的农场得到一个最大的正方形(Bessie不是必须参与作为正方形的四个顶点之一)。

inputFormat:
第 $1$ 行：一个单独的整数，$N$（$2 \leq N \leq 100$）。

第 $2 \sim (N-1)$ 行：第 $i-1$ 行使用 $N$ 个字符描述区域的第 $i$ 行。其中，`J`代表此点被 John 的牛占据，`B` 代表此点被 Bob 的牛占据，而 `*` 代表一个未被占据的点。输入保证至少有一个未被占据的点。

outputFormat: 输出一个整数，表示John的农场所能达到的最大面积。如果无法形成正方形，则输出 $0$。


title: [USACO07DEC] Sightseeing Cows G

description:
Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time.

Fortunately, they have a detailed city map showing the L (2 ≤ L ≤ 1000) major landmarks (conveniently numbered 1.. L) and the P (2 ≤ P ≤ 5000) unidirectional cow paths that join them. Farmer John will drive the cows to a starting landmark of their choice, from which they will walk along the cow paths to a series of other landmarks, ending back at their starting landmark where Farmer John will pick them up and take them back to the farm. Because space in the city is at a premium, the cow paths are very narrow and so travel along each cow path is only allowed in one fixed direction.

While the cows may spend as much time as they like in the city, they do tend to get bored easily. Visiting each new landmark is fun, but walking between them takes time. The cows know the exact fun values Fi (1 ≤ Fi ≤ 1000) for each landmark i.

The cows also know about the cowpaths. Cowpath i connects landmark L1i to L2i (in the direction L1i -> L2i ) and requires time Ti (1 ≤ Ti ≤ 1000) to traverse.

In order to have the best possible day off, the cows want to maximize the average fun value per unit time of their trip. Of course, the landmarks are only fun the first time they are visited; the cows may pass through the landmark more than once, but they do not perceive its fun value again. Furthermore, Farmer John is making the cows visit at least two landmarks, so that they get some exercise during their day off.

Help the cows find the maximum fun value per unit time that they can achieve.

inputFormat:
\* Line 1: Two space-separated integers: L and P

\* Lines 2..L+1: Line i+1 contains a single one integer: Fi

\* Lines L+2..L+P+1: Line L+i+1 describes cow path i with three space-separated integers: L1i , L2i , and Ti

outputFormat: \* Line 1: A single number given to two decimal places (do not perform explicit rounding), the maximum possible average fun per unit time, or 0 if the cows cannot plan any trip at all in accordance with the above rules.

translation:
给你一张 $n$ 点 $m$ 边的有向图，第 $i$ 个点点权为 $F_i$，第 $i$ 条边边权为 $T_i$。

找一个环，设环上的点组成的集合为 $S$，环的边组成的集合为 $E$，最大化 $\dfrac{\sum_{u\in S}F_u}{\sum_{e\in E}T_e}$。

数据范围：$1\leq n,F_i,T_i\leq 10^3$，$1\leq m\leq 5\times10^3$。


title: [USACO07DEC] Gourmet Grazers G

description:
Like so many others, the cows have developed very haughty tastes and will no longer graze on just any grass. Instead, Farmer John must purchase gourmet organic grass at the Green Grass Grocers store for each of his N (1 ≤ N ≤ 100,000) cows.

Each cow i demands grass of price at least Ai (1 ≤ Ai ≤ 1,000,000,000) and with a greenness score at least Bi (1 ≤ Bi ≤ 1,000,000,000). The GGG store has M (1 ≤ M ≤ 100,000) different types of grass available, each with a price Ci (1 ≤ Ci ≤ 1,000,000,000) and a greenness score of Di (1 ≤ Di ≤ 1,000,000,000). Of course, no cow would sacrifice her individuality, so no two cows can have the same kind of grass.

Help Farmer John satisfy the cows' expensive gourmet tastes while spending as little money as is necessary.

inputFormat:
\* Line 1: Two space-separated integers: N and M.

\* Lines 2..N+1: Line i+1 contains two space-separated integers: Ai and Bi

\* Lines N+2..N+M+1: Line i+N+1 contains two space-separated integers: Ci and Di

outputFormat: \* Line 1: A single integer which is the minimum cost to satisfy all the cows. If that is not possible, output -1.

translation:
### 题目描述

约翰的奶牛对食物越来越挑剔了。现在，商店有 $m$ 份牧草可供出售，奶牛食量很大，每份牧草仅能供一头奶牛食用。第 $i$ 份牧草的价格为 $p_i$，口感为 $q_i$。

约翰一共有 $n$ 头奶牛，他要为每头奶牛订购一份牧草，第 $i$ 头奶牛要求 它的牧草价格不低于 $a_i$，口感不低于 $b_i$。请问，约翰应该如何为每头奶牛选择牧草，才能让他花的钱最少？

### 输入格式

第一行，两个整数 $n$ 和 $m$。

第 $2\sim n+1$ 行，第 $i+1$ 行两个整数 $a_i$ 和 $b_i$。

第 $n+2\sim n+m+1$ 行，第 $i+n+1$ 行两个整数 $c_i$ 和 $d_i$。

含义见题面所述。

### 输出格式

输出仅一行，代表能够满足所有奶牛要求所要花的钱的最小值。如果不能够满足所有奶牛的要求，输出 `-1`。

### 数据范围

对于 $100\%$ 的数据，满足 $1\leqslant n\leqslant 10^5$，$1\leqslant a_i,b_i,c_i,d_i\leqslant 10^9$。


title: [USACO07DEC] Best Cow Line G

background: *本题和 [2007 年 11 月月赛银组同名题目](/problem/P6140) 在题意上一致，唯一的差别是数据范围。*

description:
Farmer John 打算带领 $N$（$1 \leq N \leq 5 \times 10^5$）头奶牛参加一年一度的”全美农场主大奖赛“。在这场比赛中，每个参赛者必须让他的奶牛排成一列，然后带领这些奶牛从裁判面前依此走过。

今年，竞赛委员会在接受报名时，采用了一种新的登记规则：取每头奶牛名字的首字母，按照它们在队伍中的次序排成一列。将所有队伍的名字按字典序升序排序，从而得到出场顺序。

FJ 由于事务繁忙，他希望能够尽早出场。因此他决定重排队列。

他的调整方式是这样的：每次，他从原队列的首端或尾端牵出一头奶牛，将她安排到新队列尾部。重复这一操作直到所有奶牛都插入新队列为止。

现在请你帮 FJ 算出按照上面这种方法能排出的字典序最小的队列。

inputFormat:
第一行一个整数 $N$。

接下来 $N$ 行每行一个大写字母，表示初始队列。

outputFormat:
输出一个长度为 $N$ 的字符串，表示可能的最小字典序队列。

每输出 $80$ 个字母需要一个换行。


title: [USACO07DEC] Charm Bracelet S

description:
Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

有 $N$ 件物品和一个容量为 $M$ 的背包。第 $i$ 件物品的重量是 $W_i$，价值是 $D_i$。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

第一行：物品个数 $N$ 和背包大小 $M$。

第二行至第 $N+1$ 行：第 $i$ 个物品的重量 $W_i$ 和价值 $D_i$。

outputFormat:
\* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

输出一行最大价值。


title: [USACO07DEC] Building Roads S

description:
Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.

Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (Xi, Yi) on the plane (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.

给定 $n$ 个点的坐标，第 $i$ 个点的坐标为 $(x_i,y_i)$，这 $n$ 个点编号为 $1$ 到 $n$。给定 $m$ 条边，第 $i$ 条边连接第 $u_i$ 个点和第 $v_i$ 个点。现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N+1: Two space-separated integers: Xi and Yi

\* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.

第一行两个整数 $n,m$ 代表点数与边数。
接下来 $n$ 行每行两个整数 $x_i,y_i$ 代表第 $i$ 个点的坐标。
接下来 $m$ 行每行两个整数 $u_i,v_i$ 代表第 $i$ 条边连接第 $u_i$ 个点和第 $v_i$ 个点。

outputFormat:
\* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.

一行一个实数代表添加的边的最小长度，要求保留两位小数，为了避免误差， 请用 $64$ 位实型变量进行计算。

hint:
### 数据规模与约定

对于 $100\%$ 的整数，$1 \le n,m \le 1000$，$1 \le x_i,y_i \le 10^6$，$1 \le u_i,v_i \le n$。

### 说明

Translated by 一只书虫仔。


title: [USACO07DEC] Mud Puddles S

description:
Farmer John is leaving his house promptly at 6 AM for his daily milking of Bessie. However, the previous evening saw a heavy rain, and the fields are quite muddy. FJ starts at the point (0, 0) in the coordinate plane and heads toward Bessie who is located at (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500). He can see all N (1 ≤ N ≤ 10,000) puddles of mud, located at points (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) on the field. Each puddle occupies only the point it is on.

Having just bought new boots, Farmer John absolutely does not want to dirty them by stepping in a puddle, but he also wants to get to Bessie as quickly as possible. He's already late because he had to count all the puddles. If Farmer John can only travel parallel to the axes and turn at points with integer coordinates, what is the shortest distance he must travel to reach Bessie and keep his boots clean? There will always be a path without mud that Farmer John can take to reach Bessie.

inputFormat:
\* Line 1: Three space-separate integers: X, Y, and N.

\* Lines 2..N+1: Line i+1 contains two space-separated integers: Ai and Bi

outputFormat: \* Line 1: The minimum distance that Farmer John has to travel to reach Bessie without stepping in mud.

translation:
清早 $6$ 点，Farmer John 就离开了他的屋子，开始了他的例行工作：为贝茜挤奶。前一天晚上，整个农场刚经受过一场瓢泼大雨的洗礼，于是不难想见，FJ 现在面对的是一大片泥泞的土地。FJ 的屋子在平面坐标 $(0,0)$ 的位置，贝茜所在的牛棚则位于坐标 $(X,Y)$（$-500 \le X,Y \le 500$）处。当然，FJ 也看到了地上的所有 $N$（$1 \le N \le 10 ^ 4$）个泥塘，第 $i$ 个泥塘的坐标为 $(A_i,B_i)$（$-500 \le A_i,B_i \le 500$）。

每个泥塘都只占据了它所在的那个格子。 FJ 自然不愿意弄脏他新买的靴子，但他同时想尽快到达贝茜所在的位置。为了数那些讨厌的泥塘，他已经耽搁了一些时间了。如果 Farmer John 只能平行于坐标轴移动，并且只在 $X,Y$ 均为整数的坐标处转弯，那么他从屋子门口出发，最少要走多少路才能到贝茜所在的牛棚呢？你可以认为从 FJ 的屋子到牛棚总是存在至少一条不经过任何泥塘的路径。


title: [USACO07FEB] Building A New Barn G

description:
After scrimping and saving for years, Farmer John has decided to build a new barn. He wants the barn to be highly accessible, and he knows the coordinates of the grazing spots of all N (2 ≤ N ≤ 10,000 cows. Each grazing spot is at a point with integer coordinates (Xi, Yi) (-10,000 ≤ Xi ≤ 10,000; -10,000 ≤ Yi ≤ 10,000). The hungry cows never graze in spots that are horizontally or vertically adjacent.

The barn must be placed at integer coordinates and cannot be on any cow's grazing spot. The inconvenience of the barn for any cow is given the Manhattan distance formula | X - Xi | + | Y - Yi|, where (X, Y) and (Xi, Yi) are the coordinates of the barn and the cow's grazing spot, respectively. Where should the barn be constructed in order to minimize the sum of its inconvenience for all the cows?
给出平面上n个不相邻的点，要求到这n个点的曼哈顿距离之和最小的点的个数ans2，和这个最小距离ans1。

inputFormat:
Line 1: A single integer: N

Lines 2..N+1: Line i+1 contains two space-separated integers which are the grazing location (Xi, Yi) of cow i

outputFormat: Line 1: Two space-separated integers: the minimum inconvenience for the barn and the number of spots on which Farmer John can build the barn to achieve this minimum.

hint: The minimum inconvenience is 10, and there are 4 spots that Farmer John can build the farm to achieve this: (0, -1), (0, 0), (1, 0), and (1, 1).


title: [USACO07FEB] The Cow Lexicon S

description:
Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters 'a'..'z'. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said "browndcodw". As it turns out, the intended message was "browncow" and the two letter "d"s were noise from other parts of the barnyard.

The cows want you to help them decipher a received message (also containing only characters in the range 'a'..'z') of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.

inputFormat:
Line 1: Two space-separated integers, respectively: W and L

Line 2: L characters (followed by a newline, of course): the received message

Lines 3..W+2: The cows' dictionary, one word per line

• 第1行:两个用空格隔开的整数,W和L.

• 第2行:一个长度为L的字符串,表示收到的信息.

• 第3行至第W+2行:奶牛的字典,每行一个词.

outputFormat:
Line 1: a single integer that is the smallest number of characters that need to be removed to make the message a sequence of dictionary words.

一个整数,表示最少去掉几个字母就可以使之变成准确的"牛语".

translation:
奶牛有她们自己的字典，里面的有 $W$（$1 \le W \le 600$）个词，每个词的长度不超过 $25$，且由小写字母组成。她们在交流时，由于各种原因，用词总是不那么准确。比如，贝茜听到有人对她说 `browndcodw`，确切的意思是 `browncow`，多出了两个 `d`。这两个 `d` 大概是身边的噪音。

奶牛们发觉辨认那些奇怪的信息很费劲，所以她们就想让你帮忙辨认一条收到的消息，即一个只包含小写字母且长度为 $L$（$1 \le L \le 300$）的字符串。有些时候，这个字符串里会有多余的字母，你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的"牛语"（即奶牛字典中某些词拼接成的一个序列）。

samples:
6 10
browndcodw
cow
milk
white
black
brown
farmer

hint: 感谢@ws\_fuweidong 提供完整题面


title: [USACO07JAN] Problem Solving G

description:
In easier times, Farmer John's cows had no problems. These days, though, they have problems, lots of problems; they have P (1 ≤ P ≤ 300) problems, to be exact. They have quit providing milk and have taken regular jobs like all other good citizens. In fact, on a normal month they make M (1 ≤ M ≤ 1000) money.

Their problems, however, are so complex they must hire consultants to solve them. Consultants are not free, but they are competent: consultants can solve any problem in a single month. Each consultant demands two payments: one in advance (1 ≤ payment ≤ M) to be paid at the start of the month problem-solving is commenced and one more payment at the start of the month after the problem is solved (1 ≤ payment ≤ M). Thus, each month the cows can spend the money earned during the previous month to pay for consultants. Cows are spendthrifts: they can never save any money from month-to-month; money not used is wasted on cow candy.

Since the problems to be solved depend on each other, they must be solved mostly in order. For example, problem 3 must be solved before problem 4 or during the same month as problem 4.

Determine the number of months it takes to solve all of the cows' problems and pay for the solutions.

inputFormat:
Line 1: Two space-separated integers: M and P.

Lines 2..P+1: Line i+1 describes problem i with two space-separated integers: Bi and Ai. Bi is the payment to the consult BEFORE the problem is solved; Ai is the payment to the consult AFTER the problem is solved.

outputFormat: Line 1: The number of months it takes to solve and pay for all the cows' problems.

translation:
在经济状况较好的时候，FJ 的奶牛没有任何问题。但如今，它们有 $P$（$1 \le P \le 300$）个问题。他们不再提供牛奶，而是像所有其他好公民一样找到了固定的工作。事实上，在一个正常的月份，他们赚了 $M$（$1 \le M \le 1000$）元钱。

然而，他们的问题非常复杂，他们必须聘请顾问来解决。咨询师不是免费的，但他们很有能力。咨询师可以在一个月内解决任何问题。每个咨询师要求两次付款，一次是在开始解决问题的月初提前支付 $a_i$ 元（$1 \le a_i \le M$），另一次是在问题解决后的月初再支付 $b_i$ 元（$1 \le b_i \le M$），这样奶牛每个月就可以用上个月赚的钱来支付咨询师的费用。

由于所要解决的问题是相互依存的，所以它们必须基本上按顺序解决。例如，问题 $3$ 必须在问题 $4$ 之前解决，或者在问题 $4$ 的同一个月内解决。

确定解决奶牛所有问题所需的月数，并支付解决方案的费用。

注意：奶牛不会存钱，每个月赚到的钱没有用完就会消失。


title: [USACO07JAN] Cow School G

description:
Bessy is going to school and doing well. She has taken N (1 ≤ N ≤ 5000 -- except one case where 1 ≤ N ≤ 50,000) tests and recorded the scores (Ti points out of Pi points for test i; 0 ≤ Ti ≤ Pi < 40,000; 0 < Pi) as this task's input.

Her teacher will drop the D tests with the lowest percentage (Ti⁄Pi) before calculating Bessie's final grade (which is the sum of the remaining test score points over the sum of the remaining total test points). Bessy is good at math and quickly realizes that this does not benefit her as much as it might.

To prove her point, Bessy wants to find all values of D for which she could have ended up with a higher grade by choosing to drop different tests than the teacher would have. Help her by finding and printing all values of D for which this is possible.

Bessy has noted that, amazingly, she has never scored the same percentage on two different tests.

一个人参加了 $N$ 场考试，第 $i$ 场满分为 $P_i$，其得分为 $T_i$。现在要删去其中 $D$ 次考试的成绩，用剩下的总得分除以剩下的满分之和，作为其最终成绩。问对于哪些 $D$ 而言，删除得分比（即 $\dfrac{T_i}{P_i}$）最小的 $D$ 场得到的最终成绩不是最优的（用其他方法可以得到更高的最终成绩）。

inputFormat:
Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains two space-separated integers: Ti and Pi

outputFormat:
Line 1: A single integer K (0 ≤ K ≤ N) that is the number of values of D for which Bessy could have ended up with a higher grade by dropping a different set of D tests than the teacher.

Lines 2..K+1: The values of D for which this is true, in ascending numerical order.


title: [USACO07JAN] Protecting the Flowers S

description:
Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cluster of cows was in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport each cow back to its own barn.

Each cow i is at a location that is Ti minutes (1 ≤ Ti ≤ 2,000,000) away from its own barn. Furthermore, while waiting for transport, she destroys Di (1 ≤ Di ≤ 100) flowers per minute. No matter how hard he tries, FJ can only transport one cow at a time back to her barn. Moving cow i to its barn requires 2 × Ti minutes (Ti to get there and Ti to return). FJ starts at the flower patch, transports the cow to its barn, and then walks back to the flowers, taking no extra time to get to the next cow that needs transport.

Write a program to determine the order in which FJ should pick up the cows so that the total number of flowers destroyed is minimized.

有 $n$ 头奶牛跑到 FJ 的花园里去吃花儿了，它们分别在距离牛圈 $T_i$（这里指 FJ 到那里需要 $T_i$ 分钟) 处吃花，每分钟会吃掉 $D_i$ 朵花，FJ 现在要将它们给弄回牛圈，但是他每次只能弄一头回去，来回用时总共为 $2 \times T_i$ 分钟，在这段时间内，其它的奶牛会继续吃 FJ 的花，速度保持不变，当然正在被赶回牛圈的奶牛不能继续吃了。现在求在最好的方案下奶牛吃掉花的最小朵数。

inputFormat:
Line 1: A single integer N

Lines 2..N+1: Each line contains two space-separated integers, Ti and Di, that describe a single cow's characteristics

outputFormat: Line 1: A single integer that is the minimum number of destroyed flowers

hint: FJ returns the cows in the following order: 6, 2, 3, 4, 1, 5. While he is transporting cow 6 to the barn, the others destroy 24 flowers; next he will take cow 2, losing 28 more of his beautiful flora. For the cows 3, 4, 1 he loses 16, 12, and 6 flowers respectively. When he picks cow 5 there are no more cows damaging the flowers, so the loss for that cow is zero. The total flowers lost this way is 24 + 28 + 16 + 12 + 6 = 86.


title: [USACO07JAN] Tallest Cow S

description:
FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only the height H (1 ≤ H ≤ 1,000,000) of the tallest cow along with the index I of that cow.

FJ has made a list of R (0 ≤ R ≤ 10,000) lines of the form "cow 17 sees cow 34". This means that cow 34 is at least as tall as cow 17, and that every cow between 17 and 34 has a height that is strictly smaller than that of cow 17.

For each cow from 1..N, determine its maximum possible height, such that all of the information given is still correct. It is guaranteed that it is possible to satisfy all the constraints.

inputFormat:
Line 1: Four space-separated integers: N, I, H and R

Lines 2..R+1: Two distinct space-separated integers A and B (1 ≤ A, B ≤ N), indicating that cow A can see cow B.

outputFormat: Lines 1..N: Line i contains the maximum possible height of cow i.

translation:
**【题目描述】**

FarmerJohn 有n头牛，它们按顺序排成一列。FarmerJohn 只知道其中最高的奶牛的序号及它的高度，其他奶牛的高度都是未知的。现在 FarmerJohn 手上有 $R$ 条信息，每条信息上有两头奶牛的序号（$a$ 和 $b$），其中 $b$ 奶牛的高度一定大于等于 $a$ 奶牛的高度，且 $a, b$之间的所有奶牛的高度都比 $a$ 小。现在 FarmerJohn 想让你根据这些信息求出每一头奶牛的可能的最大的高度。（数据保证有解）

**【输入格式】**

第一行：四个以空格分隔的整数：$n, i, h, R$（$n$ 和 $R$ 意义见题面；$i$ 和 $h$ 表示第 $i$ 头牛的高度为 $h$，他是最高的奶牛）

接下来 $R$ 行：两个不同的整数 $a$ 和 $b$（$1 \le a, b \le n$）

**【输出格式】**

一共 $n$ 行，表示每头奶牛的最大可能高度.

**【数据范围】**

$1 \le n \le 10000$，$1 \le h \le 1000000$，$0 \le R \le 10000$

Translate provided by @酥皮


title: [USACO07JAN] Balanced Lineup G

description:
For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 180,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

每天,农夫 John 的 $n(1\le n\le 5\times 10^4)$ 头牛总是按同一序列排队。

有一天, John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了 $q(1\le q\le 1.8\times10^5)$ 个可能的牛的选择和所有牛的身高 $h_i(1\le h_i\le 10^6,1\le i\le n)$。他想知道每一组里面最高和最低的牛的身高差。

inputFormat:
Line 1: Two space-separated integers, N and Q.

Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i

Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

第一行两个数 $n,q$。

接下来 $n$ 行，每行一个数 $h_i$。

再接下来 $q$ 行，每行两个整数 $a$ 和 $b$，表示询问第 $a$ 头牛到第 $b$ 头牛里的最高和最低的牛的身高差。

outputFormat:
Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

输出共 $q$ 行，对于每一组询问，输出每一组中最高和最低的牛的身高差。


title: [USACO07MAR] Ranking the Cows G

description:
Each of Farmer John's N cows (1 ≤ N ≤ 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest.

FJ has already compared the milk output rate for M (1 ≤ M ≤ 10,000) pairs of cows. He wants to make a list of C additional pairs of cows such that, if he now compares those C pairs, he will definitely be able to deduce the correct ordering of all N cows. Please help him determine the minimum value of C for which such a list is possible.

FJ想按照奶牛产奶的能力给她们排序。现在已知有N头奶牛（1 ≤ N ≤ 1,000）。FJ通过比较，已经知道了M（1 ≤ M ≤ 10,000）对相对关系。每一对关系表示为“X Y”，意指X的产奶能力强于Y。现在FJ想要知道，他至少还要调查多少对关系才能完成整个排序。

inputFormat:
Line 1: Two space-separated integers: N and M

Lines 2..M+1: Two space-separated integers, respectively: X and Y. Both X and Y are in the range 1...N and describe a comparison where cow X was ranked higher than cow Y.

outputFormat: Line 1: A single integer that is the minimum value of C.

hint: From the information in the 5 test results, Farmer John knows that since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has the highest rank. However, he needs to know whether cow 1 > cow 3 to determine the cow with the second highest rank. Also, he will need one more question to determine the ordering between cow 4 and cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1 has higher rank than cow 3. He will have to ask three questions in order to be sure he has the rankings: "Is cow 1 > cow 3?  Is cow 4 > cow 5? Is cow 5 > cow 3?"


title: [USACO07MAR] Face The Right Way G

description:
Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same \*location\* as before, but ends up facing the \*opposite direction\*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

$N$ 头牛排成一列 $1 \le N \le 5000$。每头牛或者向前或者向后。为了让所有牛都面向前方，农夫每次可以将 $K$ 头连续的牛转向 $1 \le K \le N$，求使操作次数最小的相应 $K$ 和最小的操作次数 $M$。$F$ 为朝前，$B$ 为朝后。

请在一行输出两个数字 $K$ 和 $M$，用空格分开。

inputFormat:
Line 1: A single integer: N

Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

outputFormat: Line 1: Two space-separated integers: K and M

hint: For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)


title: [USACO07MAR] Cow Traffic S

description:
The bovine population boom down on the farm has caused serious congestion on the cow trails leading to the barn. Farmer John has decided to conduct a study to find the bottlenecks in order to relieve the 'traffic jams' at milking time.

The pasture contains a network of M (1 ≤ M ≤ 50,000) one-way trails, each of which connects exactly two different intersections from the set of N (1 ≤ N ≤ 5,000) intersections conveniently numbered 1..N; the barn is at intersection number N. Each trail connects one intersection point to another intersection point with a higher number. As a result, there are no cycles and, as they say on the farm, all trails lead to the barn. A pair of intersection points might be connected by more than one trail.

During milking time rush hour, the cows start from their respective grazing locations and head to the barn. The grazing locations are exactly those intersection points with no trails connecting into them. Each cow traverses a 'path', which is defined as a sequence of trails from a grazing location to the barn.

Help FJ finding the busiest trail(s) by computing the largest number of possible paths that contain any one trail. The answer is guaranteed to fit in a signed 32-bit integer.

随着牛的数量增加，农场的道路的拥挤现象十分严重，特别是在每天晚上的挤奶时间。为了解决这个问题，FJ决定研究这个问题，以能找到导致拥堵现象的瓶颈所在。

牧场共有M条单向道路，每条道路连接着两个不同的交叉路口，为了方便研究，FJ将这些交叉路口编号为1..N,而牛圈位于交叉路口N。任意一条单向道路的方向一定是是从编号低的路口到编号高的路口，因此农场中不会有环型路径。同时，可能存在某两个交叉路口不止一条单向道路径连接的情况。

在挤奶时间到来的时候，奶牛们开始从各自的放牧地点回到牛圈。放牧地点是指那些没有道路连接进来的路口（入度为0的顶点）。

现在请你帮助fj通过计算从放牧点到达牛圈的路径数目来找到最繁忙的道路（答案保证是不超过32位整数）。

inputFormat:
Line 1: Two space-separated integers: N and M.

Lines 2..M+1: Two space-separated intersection points.

outputFormat: Line 1: The maximum number of paths passing through any one trail.

hint:
Here are the four possible paths that lead to the barn:

1 3 4 6 7

1 3 5 6 7

2 3 4 6 7

2 3 5 6 7


title: [USACO07MAR] Monthly Expense S

description:
Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ moneyi ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.

FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.

FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

给出农夫在n天中每天的花费，要求把这n天分作m组，每组的天数必然是连续的，要求分得各组的花费之和应该尽可能地小，最后输出各组花费之和中的最大值

inputFormat:
Line 1: Two space-separated integers: N and M

Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day

outputFormat: Line 1: The smallest possible monthly limit Farmer John can afford to live with.

hint: If Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit.


title: [USACO07NOV] Telephone Wire G

description:
Farmer John's cows are getting restless about their poor telephone service; they want FJ to replace the old telephone wire with new, more efficient wire. The new wiring will utilize N (2 ≤ N ≤ 100,000) already-installed telephone poles, each with some heighti meters (1 ≤ heighti ≤ 100). The new wire will connect the tops of each pair of adjacent poles and will incur a penalty cost C × the two poles' height difference for each section of wire where the poles are of different heights (1 ≤ C ≤ 100). The poles, of course, are in a certain sequence and can not be moved.

Farmer John figures that if he makes some poles taller he can reduce his penalties, though with some other additional cost. He can add an integer X number of meters to a pole at a cost of X2.

Help Farmer John determine the cheapest combination of growing pole heights and connecting wire so that the cows can get their new and improved service.

给出若干棵树的高度，你可以进行一种操作：把某棵树增高h，花费为h\*h。

操作完成后连线，两棵树间花费为高度差\*定值c。

求两种花费加和最小值。

inputFormat:
\* Line 1: Two space-separated integers: N and C

\* Lines 2..N+1: Line i+1 contains a single integer: heighti

outputFormat: \* Line 1: The minimum total amount of money that it will cost Farmer John to attach the new telephone wire.


title: [USACO07NOV] Cow Relays G

description:
For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.

Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi  ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.

To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.

Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.

给出一张无向连通图，求S到E经过k条边的最短路。

inputFormat:
\* Line 1: Four space-separated integers: N, T, S, and E

\* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i

outputFormat: \* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.

translation:
给定一张 $T$ 条边的无向连通图，求从 $S$ 到 $E$ 经过 $N$ 条边的最短路长度。
### 输入格式
第一行四个正整数 $N,T,S,E$ ，意义如题面所示。

接下来 $T$ 行每行三个正整数 $w,u,v$ ，分别表示路径的长度，起点和终点。
### 输出格式
一行一个整数表示图中从 $S$ 到 $E$ 经过 $N$ 条边的最短路长度。
### 数据范围
对于所有的数据，保证 $1\le N\le 10^6$，$2\le T\le 100$。

所有的边保证 $1\le u,v\le 1000$，$1\le w\le 1000$。


title: [USACO07NOV] Sunscreen G

description:
To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn't tan at all........

The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.

What is the maximum number of cows that can protect themselves while tanning given the available lotions?

有C个奶牛去晒太阳 (1 <=C <= 2500)，每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值，太大就晒伤了，太小奶牛没感觉。

而刚开始的阳光的强度非常大，奶牛都承受不住，然后奶牛就得涂抹防晒霜，防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。

那么为了不让奶牛烫伤，又不会没有效果。

给出了L种防晒霜。每种的数量和固定的阳光强度也给出来了

每个奶牛只能抹一瓶防晒霜，最后问能够享受晒太阳的奶牛有几个。

inputFormat:
\* Line 1: Two space-separated integers: C and L

\* Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPFi and maxSPFi

\* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri

outputFormat: A single line with an integer that is the maximum number of cows that can be protected while tanning


title: [USACO07NOV] Cow Hurdles S

description:
Farmer John wants the cows to prepare for the county jumping competition, so Bessie and the gang are practicing jumping over hurdles. They are getting tired, though, so they want to be able to use as little energy as possible to jump over the hurdles.

Obviously, it is not very difficult for a cow to jump over several very short hurdles, but one tall hurdle can be very stressful. Thus, the cows are only concerned about the height of the tallest hurdle they have to jump over.

The cows' practice room has $N$ stations, conveniently labeled $1,\dots,N$. A set of $M$ one-way paths connects pairs of stations; the paths are also conveniently labeled $1,\dots,M$. Path $i$ travels from station $S_i$ to station $E_i$ and contains exactly one hurdle of height $H_i$. Cows must jump hurdles in any path they traverse.

The cows have $T$ tasks to complete. Task $i$ comprises two distinct numbers, $A_i$ and $B_i$, which connote that a cow has to travel from station $A_i$ to station $B_i$ (by traversing over one or more paths over some route). The cows want to take a path the minimizes the height of the tallest hurdle they jump over when traveling from $A_i$ to $B_i$ . Your job is to write a program that determines the path whose tallest hurdle is smallest and report that height.

Farmer John 想让她的奶牛准备郡级跳跃比赛，Bessie 和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。

奶牛的训练场中有 $N$ 个站台，分别标记为 $1,\dots,N$。所有站台之间有 $M$ 条单向路径，第 $i$ 条路经是从站台 $S_i$ 开始，到站台 $E_i$，其中最高的栏的高度为 $H_i$。无论如何跑，奶牛们都要跨栏。

奶牛们有 $T$ 个训练任务要完成。第 $i$ 个任务包含两个数字 $A_i$ 和 $B_i$，表示奶牛必须从站台 $A_i$ 跑到站台 $B_i$，可以路过别的站台。奶牛们想找一条路径从站台 $A_i$ 到站台 $B_i$，使路径上最高的栏的高度最小。 你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

inputFormat:
\* Line $1$: Three space-separated integers: $N$, $M$, and $T$

\* Lines $2,\dots,M+1$: Line $i+1$ contains three space-separated integers: $S_i$ , $E_i$ , and $H_i$

\* Lines $M+2,\dots,M+T+1$: Line $i+M+1$ contains two space-separated integers that describe task $i$: $A_i$ and $B_i$

第一行：三个空格隔开的整数 $N, M, T$。

接下来 $M$ 行：第 $i$ 行包含三个空格隔开的整数 $S_i, E_i, H_i$。

接下来 $T$ 行：第 $i$ 行包含两个空格隔开的整数，表示任务 $i$ 的起始站台和目标站台 $A_i, B_i$。

outputFormat:
\* Lines $1,\dots,T$: Line $i$ contains the result for task $i$ and tells the smallest possible maximum height necessary to travel between the stations. Output `-1` if it is impossible to travel between the two stations.

$T$ 行：第 $i$ 行为一个整数，表示任务 $i$ 路径上最高的栏的高度的最小值。如果无法到达，输出 `-1`。

hint:
对于 $100\%$ 的数据，$1 \le N \le 300$，$1 \le M \le 2.5 \times 10^4$，$1 \le H_i \le 1 \times 10^6$，$1 \le T \le 4 \times 10^4$，$1 \le A_i,B_i \le N$。

感谢 @gaozhiyong @_Cppsteve_ 提供翻译


title: [USACO07NOV] Milking Time S

description:
Bessie 可以在接下来 $N$ 个小时内产奶，为了方便，我们把这 $N$ 个小时 $1\dots N$ 编号。

FJ 在这 $N$ 个小时内有 $M$ 段时间可以来给 Bessie 挤奶，第 $i$ 段时间从 $Start_i$ 开始到 $End_i$ 结束，可以得到 $Eff_i$ 加仑牛奶。

每次 FJ 给 Bessie 挤奶之后，Bessie 都要休息 $R$ 个小时，FJ 才能开始下一次挤奶。

现在，FJ 需要您计算出 Bessie 在这 $N$ 个小时内最多产多少奶。

inputFormat:
第一行有三个整数，分别表示 $N,M,R$。

第 $2\dots M+1$ 行，第 $i+1$ 行有三个整数 $Start_i,End_i,Eff_i$，描述一段挤奶的时间。

outputFormat: 输出一行一个整数表示答案。

hint:
#### 数据规模与约定
对于全部的测试点，保证 $1\le N\le 10^6$，$1\le M\le 10^3$，$1\le Start_i<end_i\le N$，$1\le Eff_i\le 10^6$。


title: [USACO07OPEN] Cheapest Palindrome G

description:
Keeping track of all the cows can be a tricky task so Farmer John has installed a system to automate it. He has installed on each cow an electronic ID tag that the system will read as the cows pass by a scanner. Each ID tag's contents are currently a single string with length M (1 ≤ M ≤ 2,000) characters drawn from an alphabet of N (1 ≤ N ≤ 26) different symbols (namely, the lower-case roman alphabet).

Cows, being the mischievous creatures they are, sometimes try to spoof the system by walking backwards. While a cow whose ID is "abcba" would read the same no matter which direction the she walks, a cow with the ID "abcb" can potentially register as two different IDs ("abcb" and "bcba").

FJ would like to change the cows's ID tags so they read the same no matter which direction the cow walks by. For example, "abcb" can be changed by adding "a" at the end to form "abcba" so that the ID is palindromic (reads the same forwards and backwards). Some other ways to change the ID to be palindromic are include adding the three letters "bcb" to the begining to yield the ID "bcbabcb" or removing the letter "a" to yield the ID "bcb". One can add or remove characters at any location in the string yielding a string longer or shorter than the original string.

Unfortunately as the ID tags are electronic, each character insertion or deletion has a cost (0 ≤ cost ≤ 10,000) which varies depending on exactly which character value to be added or deleted. Given the content of a cow's ID tag and the cost of inserting or deleting each of the alphabet's characters, find the minimum cost to change the ID tag so it satisfies FJ's requirements. An empty ID tag is considered to satisfy the requirements of reading the same forward and backward. Only letters with associated costs can be added to a string.

inputFormat:
Line 1: Two space-separated integers: N and M

Line 2: This line contains exactly M characters which constitute the initial ID string

Lines 3..N+2: Each line contains three space-separated entities: a character of the input alphabet and two integers which are respectively the cost of adding and deleting that character.

outputFormat: Line 1: A single line with a single integer that is the minimum cost to change the given name tag.

translation:
### 题目描述
给定一个由 $n$ 个不同的小写字母构成的长 $m$ 的字符串 $s$。可以通过**在 $\bm{s}$ 的任意位置**增减字母将 $s$ 改为回文串。增减字母的花费不同，求最小花费。
### 输入格式
第 $1$ 行是两个整数 $n,m$。

第 $2$ 行是字符串 $s$。

接下 $n$ 行，每行一个字符 $c$ 和两个整数 $x,y$，表示添加一个 $c$ 的花费为 $x$，删除一个 $c$ 的花费为 $y$。
### 输出格式
只有 $1$ 行，表示最小花费。
### 数据范围
对于 $100\%$ 的数据，$1\le m\le2\times10^3,1\le n\le 26,0\le x,y\le 10^4$。

$\mathrm{by\ @}$[$\mathrm{Fish\_Know\_Forever}$](/user/663215)

hint: If we insert an "a" on the end to get "abcba", the cost would be 1000. If we delete the "a" on the beginning to get "bcb", the cost would be 1100. If we insert "bcb" at the begining of the string, the cost would be 350 + 200 + 350 = 900, which is the minimum.


title: [USACO07OPEN] Dining G

description:
Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.

Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a complete meal of both food and drink to as many cows as possible.

Farmer John has cooked F (1 ≤ F ≤ 100) types of foods and prepared D (1 ≤ D ≤ 100) types of drinks. Each of his N (1 ≤ N ≤ 100) cows has decided whether she is willing to eat a particular food or drink a particular drink. Farmer John must assign a food type and a drink type to each cow to maximize the number of cows who get both.

Each dish or drink can only be consumed by one cow (i.e., once food type 2 is assigned to a cow, no other cow can be assigned food type 2).

inputFormat:
Line 1: Three space-separated integers: N, F, and D

Lines 2..N+1: Each line i starts with a two integers Fi and Di, the number of dishes that cow i likes and the number of drinks that cow i likes. The next Fi integers  denote the dishes that cow i will eat, and the Di integers following that denote the drinks that cow i will drink.

outputFormat: Line 1: A single integer that is the maximum number of cows that can be fed both food and drink that conform to their wishes

translation:
有 $F$ 种食物和 $D$ 种饮料，每种食物或饮料只能供一头牛享用，且每头牛只享用一种食物和一种饮料。现在有 $n$ 头牛，每头牛都有自己喜欢的食物种类列表和饮料种类列表，问最多能使几头牛同时享用到自己喜欢的食物和饮料。

对于全部数据，$1 \le f \le 100$，$1 \le d \le 100$，$1 \le n \le 100$。

hint:
One way to satisfy three cows is:

Cow 1: no meal

Cow 2: Food #2, Drink #2

Cow 3: Food #1, Drink #1

Cow 4: Food #3, Drink #3

The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.


title: [JSOI2009] 游戏

description:
小 AA 和小 YY 得到了《喜羊羊和灰太狼》的电影票，都很想去观看，但是电影票只有一张，于是他们用智力游戏决定胜负，赢得游戏的人可以获得电影票。

在 $N \times M$ 的迷宫中有一个棋子，小 AA 首先任意选择棋子放置的位置。然后，小 YY 和小 AA 轮流将棋子移动到相邻的格子里。游戏的规则规定，在一次游戏中，同一个格子不能进入两次，且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时，游戏结束，最后一个移动棋子的玩家赢得了游戏。

例如下图所示的迷宫，迷宫中 `.` 表示棋子可以经过的格子，而 `#` 表示棋子不可以经过的格子：

```cpp
                                 .##
                                 ...
                                 #.#
```
若小 AA 将棋子放置在 $(1,1)$，则小 AA 则无论如何都无法赢得游戏。

而若小 AA 将棋子放置在 $(3,2)$ 或 $(2,3)$，则小 AA 能够赢得游戏。例如，小 AA 将棋子放置在 $(3,2)$，小 YY 只能将它移动到 $(2,2)$，此时小 AA 再将棋子移动到 $(2,3)$，就赢得了游戏。

小 AA 和小 YY 都是绝顶聪明的小朋友，且从不失误。小 AA 到底能不能赢得这场游戏，从而得到珍贵的电影票呢？

inputFormat:
输入数据首先输入两个整数 $N,M$，表示了迷宫的边长。

接下来 $N$ 行，每行 $M$ 个字符，描述了迷宫。

outputFormat:
若小 AA 能够赢得游戏，则输出一行 `WIN`，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出，每行一个。

否则输出一行 `LOSE`。


title: [USACO08FEB] Making the Grade G

description:
A straight dirt road connects two fields on FJ's farm, but it changes elevation more than FJ would like. His cows do not mind climbing up or down a single slope, but they are not fond of an alternating succession of hills and valleys. FJ would like to add and remove dirt from the road so that it becomes one monotonic slope (either sloping up or down).

You are given N integers A1, ... , AN (1 ≤ N ≤ 2,000) describing the elevation (0 ≤ Ai ≤ 1,000,000,000) at each of N equally-spaced positions along the road, starting at the first field and ending at the other. FJ would like to adjust these elevations to a new sequence B1, . ... , BN that is either nonincreasing or nondecreasing. Since it costs the same amount of money to add or remove dirt at any position along the road, the total cost of modifying the road is

|A1 - B1| + |A2 - B2| + ... + |AN - BN |Please compute the minimum cost of grading his road so it becomes a continuous slope. FJ happily informs you that signed 32-bit integers can certainly be used to compute the answer.

农夫约翰想改造一条路，原来的路的每一段海拔是$A_i$，修理后是 $B_i$，花费 $|A_i - B_i|$。我们要求修好的路是单调不升或者单调不降的。求最小花费。

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains a single integer elevation: Ai

outputFormat: \* Line 1: A single integer that is the minimum cost for FJ to grade his dirt road so it becomes nonincreasing or nondecreasing in elevation.


title: [USACO08FEB] Hotel G

description:
The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

第一行输入 $n,m$，$n$ 代表有 $n$ 个房间 $(1\leq n \leq 50,000)$，编号为 $1 \sim n$，开始都为空房，$m$ 表示以下有 $m$ 行操作 $(1\leq m < 50,000)$，以下每行先输入一个数 $i$ ，表示一种操作：

若 $i$ 为 $1$，表示查询房间，再输入一个数 $x$，表示在 $1,2,...,n$ 房间中找到长度为 $x$ 的连续空房，输出连续 $x$ 个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为 $x$ 的连续空房，输出 $0$。若找得到，在这 $x$ 个空房间中住上人。

若 $i$ 为 $2$，表示退房，再输入两个数 $x,y$ 代表房间号 $x \sim x+y-1$ 退房，即让房间为空。

你需要对每个输入 $1$ 输出对应的答案。

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di

outputFormat: \* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.


title: [USACO08FEB] Meteor Shower S

description:
Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hit. Anxious for her safety, she vows to find her way to a safe location (one that is never destroyed by a meteor) . She is currently grazing at the origin in the coordinate plane and wants to move to a new, safer location while avoiding being destroyed by meteors along her way.

The reports say that M meteors (1 ≤ M ≤ 50,000) will strike, with meteor i will striking point (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300) at time Ti (0 ≤ Ti  ≤ 1,000). Each meteor destroys the point that it strikes and also the four rectilinearly adjacent lattice points.

Bessie leaves the origin at time 0 and can travel in the first quadrant and parallel to the axes at the rate of one distance unit per second to any of the (often 4) adjacent rectilinear points that are not yet destroyed by a meteor. She cannot be located on a point at any time greater than or equal to the time it is destroyed).

Determine the minimum time it takes Bessie to get to a safe place.

inputFormat:
\* Line 1: A single integer: M

\* Lines 2..M+1: Line i+1 contains three space-separated integers: Xi, Yi, and Ti

outputFormat: \* Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.

translation:
## 题目描述
贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。

如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。

根据预报，一共有 $M$ 颗流星 $(1\leq M\leq 50,000)$ 会坠落在农场上，其中第 $i$ 颗流星会在时刻 $T_i$（$0 \leq T _ i \leq 1000$）砸在坐标为 $(X_i,Y_i)(0\leq X_i\leq 300$，$0\leq Y_i\leq 300)$ 的格子里。流星的力量会将它所在的格子，以及周围 $4$ 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。

贝茜在时刻 $0$ 开始行动，她只能在会在横纵坐标 $X,Y\ge 0$ 的区域中，平行于坐标轴行动，每 $1$ 个时刻中，她能移动到相邻的（一般是 $4$ 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 $t$ 被流星撞击或烧焦，那么贝茜只能在 $t$ 之前的时刻在这个格子里出现。 贝茜一开始在 $(0,0)$。

请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 $−1$。
## 输入格式
共 $M+1$ 行，第 $1$ 行输入一个整数 $M$，接下来的 $M$ 行每行输入三个整数分别为 $X_i, Y_i, T_i$。
## 输出格式
贝茜到达安全地点所需的最短时间，如果不可能，则为 $-1$。


title: [USACO08FEB] Eating Together S

description:
The cows are so very silly about their dinner partners. They have organized themselves into three groups (conveniently numbered 1, 2, and 3) that insist upon dining together. The trouble starts when they line up at the barn to enter the feeding area.

Each cow i carries with her a small card upon which is engraved Di (1 ≤ Di ≤ 3) indicating her dining group membership. The entire set of N (1 ≤ N ≤ 30,000) cows has lined up for dinner but it's easy for anyone to see that they are not grouped by their dinner-partner cards.

FJ's job is not so difficult. He just walks down the line of cows changing their dinner partner assignment by marking out the old number and writing in a new one. By doing so, he creates groups of cows like 111222333 or 333222111 where the cows' dining groups are sorted in either ascending or descending order by their dinner cards.

FJ is just as lazy as the next fellow. He's curious: what is the absolute mminimum number of cards he must change to create a proper grouping of dining partners? He must only change card numbers and must not rearrange the cows standing in line.

FJ的奶牛们在吃晚饭时很傻。他们把自己组织成三组（方便编号为1, 2和3），坚持一起用餐。当他们在谷仓排队进入喂食区时，麻烦就开始了。

每头奶牛都随身带着一张小卡片，小卡片上刻的是Di（1≤Di≤3）表示她属于哪一组。所有的N（1≤N≤30000）头奶牛排队吃饭，但他们并不能按卡片上的分组站好。

FJ的工作并不是那么难。他只是沿着牛的路线走下去，把旧的号码标出来，换上一个新的。通过这样做，他创造了一群奶牛，比如111222333或333222111，奶牛的就餐组按他们的晚餐卡片按升序或降序排列。

FJ就像任何人一样懒惰。他很好奇：怎样他才能进行适当的分组，使得他只要修改最少次数的数字？由于奶牛们已经很长时间没有吃到饭了，所以“哞哞”的声音到处都是，FJ只好更换卡号，而不能重新排列已经排好队的奶牛。

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i describes the i-th cow's current dining group with a single integer: Di

- 第1行：一个整数：n

- 第2~n+1行：第i-1行描述第i个奶牛目前分组。

outputFormat:
\* Line 1: A single integer representing the minimum number of changes that must be made so that the final sequence of cows is sorted in either ascending or descending order

一个整数，表示必须做出的最小变化数，以便以升序或降序排序最终序列。

hint: 感谢@一思千年 提供翻译


title: [USACO08JAN] Artificial Lake G

background: USACO 2008 January Gold

description:
The oppressively hot summer days have raised the cows' clamoring to its highest level. Farmer John has finally decided to build an artificial lake. For his engineering studies, he is modeling the lake as a two-dimensional landscape consisting of a contiguous sequence of N soon-to-be-submerged levels (1 ≤ N ≤ 100,000) conveniently numbered 1..N from left to right.

Each level i is described by two integers, its width Wi (1 ≤ Wi ≤ 1,000) and height (like a relative elevation) Hi (1 ≤ Hi ≤ 1,000,000). The heights of FJ's levels are unique. An infinitely tall barrier encloses the lake's model on the left and right. One example lake profile is shown below.

```cpp
         *             *  :
         *             *  :
         *             *  8
         *    ***      *  7
         *    ***      *  6
         *    ***      *  5
         *    **********  4 <- height
         *    **********  3
         ***************  2
         ***************  1
Level    |  1 |2|  3   |
```
In FJ's model, he starts filling his lake at sunrise by flowing water into the bottom of the lowest elevation at a rate of 1 square unit of water per minute. The water falls directly downward until it hits something, and then it flows and spreads as room-temperature water always does. As in all good models, assume that falling and flowing happen instantly. Determine the time at which each elevation's becomes submerged by a single unit of water.

```cpp
WATER              WATER OVERFLOWS
       |                       |
     * |          *      *     |      *      *            *
     * V          *      *     V      *      *            *
     *            *      *    ....    *      *~~~~~~~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
     *    *********      *~~~~*********      *~~~~*********
     *~~~~*********      *~~~~*********      *~~~~*********
     **************      **************      **************
     **************      **************      **************
     After 4 mins        After 26 mins       After 50 mins

     Lvl 1 submerged     Lvl 3 submerged     Lvl 2 submerged
```
Warning: The answer will not always fit in 32 bits.

夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点。最终，FJ决定建一个人工湖供奶牛消暑之用。为了使湖看起来更加真实，FJ决定将湖的横截面建成N(1 <= N <= 100,000)个连续的平台高低错落的组合状，所有的平台从左到右按1..N依次编号。当然咯，在湖中注入水后，这些平台都将被淹没。    平台i在设计图上用它的宽度W\_i(1 <= W\_i <= 1,000)和高度（你可以理解为该平台顶离FJ挖的地基的高度）H\_i(1 <= H\_i <= 1,000,000)来描述的。所有平台的高度都是独一无二的。湖的边缘可以视为无限高的平台。下面给出了一张FJ的设计图：

按FJ的设想，在坑挖好后，他会以1单位/分钟的速度往最低的那个平台上注水。水在离开水管后立即下落，直到撞到平台顶或是更早些时候注入的水。然后，与所有常温下的水一样，它会迅速地流动、扩散。简单起见，你可以认为这些都是在瞬间完成的。FJ想知道，对于每一个平台，它的顶部是从哪个时刻开始，与水面的距离至少为1单位长度。

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 describes level i with two space-separated integers: Wi and Hi

outputFormat: Lines 1..N: Line i contains a single integer that is the number of minutes that since sunrise when level #i is covered by water of height 1.


title: [USACO08JAN] Haybale Guessing G

description:
The cows, who always have an inferiority complex about their intelligence, have a new guessing game to sharpen their brains.

A designated 'Hay Cow' hides behind the barn and creates N (1 ≤ N ≤ 1,000,000) uniquely-sized stacks (conveniently numbered 1..N) of hay bales, each with 1..1,000,000,000 bales of hay.

The other cows then ask the Hay Cow a series of Q (1 ≤ Q ≤ 25,000) questions about the the stacks, all having the same form:

What is the smallest number of bales of any stack in the range of stack numbers Ql..Qh (1 ≤ Ql ≤ N; Ql ≤ Qh ≤ N)?The Hay Cow answers each of these queries with a single integer A whose truthfulness is not guaranteed.

Help the other cows determine if the answers given by the Hay Cow are self-consistent or if certain answers contradict others.

inputFormat:
\* Line 1: Two space-separated integers: N and Q

\* Lines 2..Q+1: Each line contains three space-separated integers that represent a single query and its reply: Ql, Qh, and A

outputFormat: \* Line 1: Print the single integer 0 if there are no inconsistencies among the replies (i.e., if there exists a valid realization of the hay stacks that agrees with all Q queries). Otherwise, print the index from 1..Q of the earliest query whose answer is inconsistent with the answers to the queries before it.

translation:
给一个长度为 $n$ 的数组 $q$ 个条件，数组中的数字互不相同，每个条件格式形如  $l_i,r_i,x_i$ 表示这个数组的区间 $[l_i,r_i]$ 内的最小值为  $x_i$，输出最早与前面的条件有矛盾的条件的编号，如果所有条件都不发生矛盾，输出 $0$。

### 输入格式

第一行两个整数，分别是  $n$ 和  $q$。

第二行至第 $q+1$ 行，每行三个整 $l_i,r_i,x_i$ 描述一个条件。

### 输出格式

仅一个整数，表示最早发生矛盾的条件的编号。如果所有条件都没有发生矛盾，输出 $0$。


title: [USACO08JAN] Cell Phone Network G

description:
Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N) so they can all communicate.

Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.

Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

Farmer John 想让他的所有牛用上手机以便相互交流。他需要建立几座信号塔在 $N$ 块草地中。已知与信号塔相邻的草地能收到信号。给你 $N-1$ 个草地 $(A,B)$ 的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

outputFormat: \* Line 1: A single integer indicating the minimum number of towers to install


title: [USACO08MAR] Land Acquisition G

description:
Farmer John 准备扩大他的农场，眼前他正在考虑购买 $N$ 块长方形的土地。

如果 FJ 单买一块土地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 $3 \times 5$ 和一块 $5 \times 3$ 的土地，他只需要支付 $5 \times 5=25$ 元， 比单买合算。

FJ 希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。

inputFormat:
第一行一个整数 $N$（$1 \leq N \leq 5 \times 10^4$）。

接下来 $N$ 行，每行两个整数 $w_i$ 和 $l_i$，代表第 $i$ 块土地的长和宽。保证土地的长和宽不超过 $10^6$。

outputFormat: 输出买下所有土地的最小费用。

hint:
将所有土地分为三组：

- 第一块土地为第一组，花费 $100 \times 1=100$；
- 第二，三块土地为第二组，花费 $20 \times 15=300$；
- 第四块土地为第三组，花费 $1 \times 100=100$；

总花费为 $500$，可以证明不存在更优的方案。


title: [USACO08MAR] Cow Jogging G

description:
贝西终于尝到了懒惰的后果，决定每周从谷仓到池塘慢跑几次来健身。当然，她不想跑得太累，所以她只打算从谷仓慢跑下山到池塘，然后悠闲地散步回谷仓。

同时，贝西不想跑得太远，所以她只想沿着通向池塘的最短路径跑步。一共有 $M$ 条道路，其中每一条都连接了两个牧场。这些牧场从 $1$ 到 $N$ 编号，如果 $X>Y$，则说明牧场 $X$ 的地势高于牧场 $Y$，即下坡的道路是从 $X$ 通向 $Y$ 的，$N$ 为贝西所在的牛棚（最高点），$1$ 为池塘（最低点）。

然而，一周之后，贝西开始对单调的路线感到厌烦，她希望可以跑不同的路线。比如说，她希望能有 $K$ 种不同的路线。同时，为了避免跑得太累，她希望这 $K$ 条路线是从牛棚到池塘的路线中最短的 $K$ 条。如果两条路线包含的道路组成的序列不同，则这两条路线被认为是不同的。

请帮助贝西算算她的训练强度，即将牧场网络里最短的 $K$ 条路径的长度分别算出来。你将会被提供一份牧场间路线的列表，每条道路用 $(X_i, Y_i, D_i)$ 表示，意为从 $X_i$ 到 $Y_i$ 有一条长度为 $D_i$ 的下坡道路。

inputFormat:
第一行三个用空格分开的整数 $N,M,K$，其中 。

第二行到第 $M+1$ 行每行有三个用空格分开的整数 $X_i,Y_i,D_i$，描述一条下坡的道路。

outputFormat: 共 $K$ 行，在第 $i$ 行输出第 $i$ 短的路线长度，如果不存在则输出 $-1$。如果出现多种有相同长度的路线，务必将其全部输出。


title: [USACO08MAR] Pearl Pairing G

description:
At Bessie's recent birthday party, she received $N(2 \le N \le 10^5,N\equiv0\pmod{2})$ pearls, each painted one of C different colors ($1\le C \le N$).

Upon observing that the number of pearls $N$ is always even, her creative juices flowed and she decided to pair the pearls so that each pair of pearls has two different colors.

Knowing that such a set of pairings is always possible for the supplied testcases, help Bessie perform such a pairing. If there are multiple ways of creating a pairing, any solution suffices.

在 Bessie 最近的生日聚会上，她收到 $N(2\le N \le 10^5,N\equiv0\pmod{2})$ 颗珍珠。一共有 $C$ 种颜色的珍珠（$1\le C \le N$），第 $i$ 种颜色的珍珠有 $C_i$ 颗。

观察到珍珠的数量 $N$ 总是偶数，她的创意来了，决定配对珍珠，使每对珍珠有两种不同的颜色。数据保证存在答案。请帮助 Bessie 执行这样的配对，如果有多种配对的方法，输出任意一种即可。

inputFormat:
Line $1$: Two space-separated integers: $N$ and $C$.

Lines $2 \ldots C+1$: Line $i+1$ tells the count of pearls with color $i$: $C_i$.

第 $1$ 行：两个空格分隔的整数：$N$ 和 $C$。

第 $2\ldots C+1$行：第 $i+1$ 为颜色 $i$ 的珍珠数 $C_i$。

outputFormat:
Lines $1\ldots \dfrac{N}{2}$: Line $i$ contains two integers $a_i$ and $b_i$ indicating that Bessie can pair two pearls with respective colors $a_i$ and $b_i$.

第 $1\ldots \dfrac{N}{2}$ 行：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，表示 Bessie 可以将各自颜色为 $a_i$ 和 $b_i$ 的两个珍珠配对。

hint:
There are $8$ pearls and $3$ different colors. Two pearls have color $\mathrm{I}$; two have color $\mathrm{II}$; four have color $\mathrm{III}$.

Bessie pairs each pearl of color $\mathrm{III}$ with one of color $\mathrm{I}$ and $\mathrm{Ii}$.

说明：有 $8$ 颗珍珠和 $3$ 种不同的颜色。两颗珍珠颜色为 $1$，两颗珍珠颜色为 $2$，四颗珍珠颜色为 $3$。

Bessie 将每颗颜色为 $3$ 的珍珠与颜色为 $1$ 和 $2$ 的珍珠配对。

感谢@[线段木](https://www.luogu.com.cn/user/33930) 提供翻译，@[PineappleSummer](https://www.luogu.com.cn/user/880187) 修正翻译以及提供 $\LaTeX$。


title: [USACO08MAR] The Loathesome Hay Baler S

description:
Farmer John has purchased the world's most loathesome hay baler. Instead of having a drive-roller that drives maybe an idler roller that drives the power take-off for the baler, it has N rollers (2 <= N <= 1050) which drive and are driven by various rollers.

FJ has meticulously cataloged data for each roller i: X\_i,Y\_i are the center of the roller (-5000 <= X\_i <= 5000; -5000 <= Y\_i <= 5000); R\_i is the roller's radius (3 <= R\_i <= 800). The drive-roller is located at 0,0; the baler power take-off is located at X\_t,Y\_t (numbers supplied in the input).

The drive-roller turns clockwise at 10,000 revolutions per hour. Your job is to determine the speeds of all the rollers that are in the power-train: from the drive-roller through the power take-off roller. Rollers that do not transfer power to the take-off roller are to be ignored. A roller of radius Rd that is turning at S rph and driving another roller of radius Rx will cause the second roller to turn at the speed -S\*Rd/Rx (where the sign denotes whether the roller is turning clockwise or counterclockwise (anticlockwise for our British friends)).

Determine the power-train path and report the sum of the absolute values of all those rollers' speeds. All the rollers in the input set except the driver-roller are driven by some other roller; power is never transferred to a roller from more than one other roller.

Report your answer as an integer that is the truncated value after summing all the speeds.

inputFormat:
\* Line 1: Three space-separated integers: N, X\_t, and Y\_t

\* Lines 2..N+1: Line i+1 describes roller i's properties: X\_i, Y\_i, and R\_i

outputFormat: \* Line 1: A single integer that is the truncated version of the sum of the absolute value of the speeds of the rollers in the power-train including the drive-roller, all the driven rollers, and the power take-off roller.

translation:
Farmer John 新买的干草打包机的内部结构大概算世界上最混乱的了，它不像普通的机器一样有明确的内部传动装置，而是 $N$ 个齿轮互相作用，每个齿轮都可能驱动着多个齿轮。 FJ 记录了对于每个齿轮 $i$，记录了它的 $3$ 个参数，以一个三元组 $(x,y,r)$ 表示，$x$ 和 $y$ 表示齿轮中心的位置坐标，$r$ 表示该齿轮的半径。

驱动齿轮的位置为 $(0,0)$，并且 FJ 也知道最终的工作齿轮位于 $(X_t,Y_t)$。 驱动齿轮顺时针转动，转速为 $10,000$ 转/小时。你的任务是，确定传动序列中所有齿轮的转速。传动序列的定义为，能量由驱动齿轮传送到工作齿轮的过程中用到的所有齿轮的集合。对能量传送无意义的齿轮都应当被忽略。

在一个半径为 $R_d$，转速为 $S$ 转/每小时的齿轮的带动下，与它相接的半径为 $R_x$ 的齿轮的转速将为 $-S\times \frac{R_d}{R_x}$ 转/小时。$S$ 前的负号的意思是，一个齿轮带动的另一个齿轮的转向会与它的转向相反。

FJ 只对整个传动序列中所有齿轮速度的绝对值之和感兴趣，你的任务也就相应转化成求这个值。机器中除了驱动齿轮以外的所有齿轮都被另外某个齿轮带动，并且不会出现 $2$ 个不同的齿轮带动同一个齿轮的情况。

### 输入格式

第一行，三个整数，分别代表 $N,X_t,Y_t$；

第 $2$ 行到第 $N+1$ 行，每行三个整数，代表一个三元组 $(x,y,r)$。

### 输出格式

输出共一行，一个整数，代表整个传动序列中所有齿轮速度的绝对值之和。

hint:
$2 \leq N \leq 1050$，$-5000 \leq x,y \leq 5000$，$3 \leq r \leq 800$。

Four rollers: the drive-roller at 0,0 with radius 10. It drives the roller above it at 0,30 with radius 20. That roller drives both the power take-off roller at 32,54 (r=20) and a random roller (not in the power train) at -40,30 (r=20).

Roller   Radius   Speed

1 (0,0)     10     10,000

2 (0,30)    20     -5,000

3 (32,54)   20      5,000

------
Sum of abs values: 20,000


title: [USACO08MAR] River Crossing S

description:
Farmer John is herding his N cows (1 <= N <= 2,500) across the expanses of his farm when he finds himself blocked by a river. A single raft is available for transportation.

FJ knows that he must ride on the raft for all crossings and that that adding cows to the raft makes it traverse the river more slowly.

When FJ is on the raft alone, it can cross the river in M minutes (1 <= M <= 1000).  When the i cows are added, it takes M\_i minutes (1 <= M\_i <= 1000) longer to cross the river than with i-1 cows (i.e., total M+M\_1 minutes with one cow, M+M\_1+M\_2 with two, etc.). Determine the minimum time it takes for Farmer John to get all of the cows across the river (including time returning to get more cows).

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N+1: Line i+1 contains a single integer: M\_i

outputFormat: \* Line 1: The minimum time it takes for Farmer John to get all of the cows across the river.

translation:
### 题目描述
农夫约翰以及他的 $N(1 \le N \le 2500)$ 头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。

由于奶牛不会划船，在整个渡河过程中，约翰必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加 $1$，FJ把木筏划到对岸就得花更多的时间。

当约翰一个人坐在木筏上，他把木筏划到对岸需要 $M(1 \le M \le 1000)$ 分钟。当木筏搭载的奶牛数目从 $i-1$ 增加到 $i$ 时，约翰得多花 $M_i(1 \le M_i \le 1000)$ 分钟才能把木筏划过河（也就是说，船上有 $1$ 头奶牛时，约翰得花 $M+M_1$ 分钟渡河；船上有 $2$ 头奶牛时，时间就变成 $M+M_1+M_2$ 分钟。后面的以此类推）。那么，约翰最少要花多少时间，才能把所有奶牛带到对岸呢？当然，这个时间得包括约翰一个人把木筏从对岸划回来接下一批的奶牛的时间。

### 输入格式
* 第一行包含 $2$ 个整型变量 $N$ 和 $M$。
* 第二行包含 $2 ... N + 1$ 个整数，第 $i + 1$ 行包含 $1$ 个整数 $M_i$。

### 输出格式
* 输出共 $1$ 行，为农夫约翰让所有奶牛过河所需的最短时间。

hint:
There are five cows. Farmer John takes 10 minutes to cross the river alone, 13 with one cow, 17 with two cows, 23 with three, 123 with four, and 124 with all five.

Farmer John can first cross with three cows (23 minutes), then return (10 minutes), and then cross with the last two (17 minutes). 23+10+17 = 50 minutes total.


title: [USACO08OPEN] Crisis on the Farm G

description:
约翰和他的奶牛组建了一只乐队“后街奶牛”，现在他们正在牧场里排练。奶牛们分成一堆一堆，共 $1000$）堆。每一堆里，$30$ 只奶牛一只踩在另一只的背上，叠成一座牛塔。牧场 里还有 $M(1 < M < 1000)$ 个高高的草垛。

作为出色的指挥家，约翰可以通过口哨指挥奶牛们移动。他的口哨有四个音，分别能使所有的牛塔向东南西北四个方向移动一格。

每一次，当一个牛塔到达了一个草垛所在的格子，牛塔最上方的奶牛就会跳到草垛上，而且不再下来，而其他奶牛仍然呈塔状站在草垛所在的格子里.当牛塔只剩一只奶牛时，这只奶牛也会跳到草垛上。

突然，约翰大惊失色：原来邻家的奶缸爆炸了！滚滚而下的牛奶正朝着约翰的牧场冲来，不久就要将牧场淹没。约翰必须马上行动，用口哨声挽救奶牛们的生命。他要指挥奶牛尽量多地跳上草操，草操上的奶牛将不会被淹死.

约翰还有 $K$ 次吹口哨的机会.那他最多还能救多少奶牛呢？请计算最多能挽救的奶牛数，以及达到这个数目约翰需要吹的口哨调子序列。序列用 $\mathtt{E,W,S,N}$ 表示东西南北。如果有多种序列能达到 要求，输出作为字符串最小的。

inputFormat:
\* Line 1: Three space-separated integers: N, M, and K

\* Lines 2..N+1: Line i+1 describes the X,Y location of a stack of 30 cows using two space-separated integers: X\_i and Y\_i

\* Lines N+2..N+M+1: Line i+N+1 describes the X,Y location of a haystack using two space-separated integers: X\_i and Y\_i

outputFormat:
\* Line 1: A single integer that is the most number of cows that can be saved.

\* Line 2: K characters, the lexicographically least sequence of commands FJ should issue to maximize the number of cows saved.

hint:
Use the 'east' whistle three times, at which point the milk floods the area.  Each haystack ends up saving 1 cow.

对于 $100\%$ 的数据，$1\le K\le 30$，$1\le N,M,X_i,Y_i\le 1000$。


title: [USACO08OPEN] Cow Neighborhoods G

description:
了解奶牛的人都知道奶牛是如何组成「奶牛社区」的。他们观察了 Farmer John 的 $N$ 头奶牛（编号为 $1 \sim N$），它们在 $X$ 和 $Y$ 坐标范围为 $1$ 的牧场上放牧，每头奶牛都在自己唯一的整数直线坐标上。

如果满足以下两个标准中的至少一个，则两头奶牛是邻居：

1. 两只奶牛的曼哈顿距离不超过 $C$，即 $|X_i - x_i| + |Y_i - y_i| \leq C$；
2. 两只奶牛有共同的邻居。即存在一只奶牛 $k$，使 $i$ 与 $k$，$j$ 与 $k$ 均同属一个群。

给定奶牛的位置和距离 $C$，确定「奶牛社区」的数量和最大的「奶牛社区」中的奶牛数量。

例如，考虑下面的牧场。 当 $C = 4$ 时，这个牧场有四个社区：左边的一个大社区，两个大小为 1 的社区，右边有一个巨大的社区，里面有 $60$ 头不同的奶牛。

```text
.....................................*.................
....*...*..*.......................***.................
......*...........................****.................
..*....*..*.......................*...*.******.*.*.....
........................*.............***...***...*....
*..*..*...*..........................*..*...*..*...*...
.....................................*..*...*..*.......
.....................................*..*...*..*.......
...*................*..................................
.*..*............................*.*.*.*.*.*.*.*.*.*.*.
.*.....*..........................*.*.*.*.*.*.*.*.*.*.*
....*..................................................
```

inputFormat:
第 $1$ 行包含两个用空格分隔的整数 $N, C$。

第 $2$ 到第 $N + 1$ 行每行包含两个用空格分隔的整数 $X_i, Y_i$，表示一头牛的坐标。

outputFormat: 共一行，为两个用空格分隔的整数，为「奶牛社区」的数量和最大的「奶牛社区」内牛的数量。

hint:
### 样例说明 #1

样例中有 $2$ 个社区，一个由前三头奶牛组成，另一个是最后一头奶牛。因此，最大的社区大小为 $3$。

### 数据范围与约定

对于 $100\%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq C \leq 10^9$，$1 \leq X_i, Y_i \leq 10^9$，$X_i, Y_i$ 均为整数。


title: [USACO08OPEN] Roads Around The Farm S

description:
Farmer John's cows have taken an interest in exploring the territory around the farm. Initially, all N (1 <= N <= 1,000,000,000) cows commence traveling down a road in one big group. Upon encountering a fork in the road, the group sometimes chooses to break into two smaller (nonempty) groups with each group continuing down one of the roads.  When one of those groups arrives at another fork, it might split again, and so on.

The cows have crafted a peculiar way of splitting: if they can split into two groups such that the sizes of the groups differ by exactly K (1 <= K <= 1000), then they will split in that way; otherwise, they stop exploring and just start grazing peacefully.

Assuming that there will always be new forks in the road, compute the final number of groups of peacefully grazing cows.

inputFormat: \* Line 1: Two space-separated integers: N and K

outputFormat: \* Line 1: A single integer representing the number of groups of grazing cows

translation:
约翰的 $ N $ 只奶牛要出发去探索牧场四周的土地。它们将沿着一条路走，一直走到三岔路口（可以认为所有的路口都是这样的）。这时候，这一群奶牛可能会分成两群，分别沿着接下来的两条路继续走。如果她们再次走到三岔路口，那么仍有可能继续分裂成两群继续走。

奶牛的分裂方式十分古怪：

如果这一群奶牛可以精确地分成两部分，这两部分的牛数恰好相差 $ K $ 头，那么在三岔路口牛群就会分裂。

否则，牛群不会分裂，她们都将在这里待下去，平静地吃草。 请计算，最终将会有多少群奶牛在平静地吃草。

数据范围：

$ 1 \le N \le 10^{9}$

$ 1 \le K \le 10^{3}$

hint:
There are 6 cows and the difference in group sizes is 2.

There are 3 final groups (with 2, 1, and 3 cows in them).

6
/ \
2   4
/ \
1   3