title: [USACO13OPEN] Photo G

description:
Farmer John has decided to assemble a panoramic photo of a lineup of his N cows (1 <= N <= 200,000), which, as always, are conveniently numbered from 1..N.  Accordingly, he snapped M (1 <= M <= 100,000) photos, each covering a contiguous range of cows: photo i contains cows a\_i through b\_i inclusive.  The photos collectively may not necessarily cover every single cow.

After taking his photos, FJ notices a very interesting phenomenon: each photo he took contains exactly one cow with spots!  FJ was aware that he had some number of spotted cows in his herd, but he had never actually counted them.  Based on his photos, please determine the maximum possible number of spotted cows that could exist in his herd.  Output -1 if there is no possible assignment of spots to cows consistent with FJ's photographic results.

农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。

于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号a\_i 到 b\_i的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。

在拍完照片后，约翰发现了一个有趣的事情：每张照片中都**有且仅有**一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

Input

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

\* Lines 2..M+1: Line i+1 contains a\_i and b\_i.

outputFormat: \* Line 1: The maximum possible number of spotted cows on FJ's farm, or -1 if there is no possible solution.

hint:
There are 5 cows and 3 photos.  The first photo contains cows 1 through 4, etc.

From the last photo, we know that either cow 3 or cow 4 must be spotted. By choosing either of these, we satisfy the first two photos as well.


title: [USACO13OPEN] Yin and Yang G

type: P

description:
Farmer John is planning his morning walk on the farm. The farm is structured like a tree: it has N barns (1 <= N <= 100,000) which are connected by N-1 edges such that he can reach any barn from any other. Farmer John wants to choose a path which starts and ends at two different barns, such that he does not traverse any edge twice. He worries that his path might be a little long, so he also wants to choose another "rest stop" barn located on this path (which is distinct from the start or the end).

Along each edge is a herd of cows, either of the Charcolais (white hair) or the Angus (black hair) variety. Being the wise man that he is, Farmer John wants to balance the forces of yin and yang that weigh upon his walk. To do so, he wishes to choose a path such that he will pass by an equal number of Charcolais herds and Angus herds-- both on the way from the start to his rest stop, and on the way from the rest stop to the end.

Farmer John is curious how many different paths he can choose that are "balanced" as described above.  Two paths are different only if they consist of different sets of edges; a path should be counted only once even if there are multiple valid "rest stop" locations along the path that make it balanced.

Please help determine the number of paths Farmer John can choose!

给出一棵n个点的树，每条边为黑色或白色。问满足以下条件的路径条数：路径上存在一个不是端点的点，使得两端点到该点的路径上两种颜色的边数都相等。

inputFormat:
\* Line 1: The integer N.

\* Lines 2..N: Three integers a\_i, b\_i and t\_i, representing the two barns that edge i connects. t\_i is 0 if the herd along that edge is Charcolais, and 1 if the  herd is Angus.

outputFormat: \* Line 1: One integer, representing the number of possible paths Farmer John can choose from.

hint:
There are 7 barns and 6 edges. The edges from 1 to 2, 2 to 4 and 2 to 5 have Charcolais herds along them.

No path of length 2 can have a suitable rest stop on it, so we can only consider paths of length 4. The only path that has a suitable rest stop is 3-1-2-5-7, with a rest stop at 2.


title: [USACO13OPEN] Figure Eight G

description:
Farmer John's cows recently received a large piece of marble, which, unfortunately, has a number of imperfections.  To describe these, we can represent the piece of marble by an N by N square grid (5 <= N <= 300), where the character '\*' represents an imperfection and '.' represents a flawless section of the marble.

The cows want to carve a number "8" in this piece of marble (cows are quite fond of the number "8" since they have cloven hooves on each of their four feet, so they can effectively count up to 8 using their "toes"). However, the cows need your help to determine the optimally placed figure eight in the piece of marble.  Here are a few properties that define a valid figure eight:

\* A figure eight consists of two rectangles, a top and a bottom. \* Both the top and bottom have at least one cell in their interior. \* The bottom edge of the top rectangle is a (not necessarily proper) subset of the top edge of the bottom rectangle.

\* The figure eight can only be carved from flawless regions of the piece of marble.

The aesthetic score of a figure eight is equal to the product of the areas enclosed by its two rectangles.  The cows wish to maximize this score.

```cpp
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
```
For example, given this piece of marble

the optimally placed eight is:

```cpp
..88888888888..
..8.........8..
..8*******..8..
.*8...*.....8.*
.*8.....*...8*.
..8.*.......8..
..8*...****.8..
.88888888888888
.8**.*..*..*..8
.8.*...**.*...8
*8.*...*......8
.8............8
.8...*..*.....8
.8.......*....8
.88888888888888
```
The top rectangle has area 6x9=54, and the bottom rectangle has area 12x6=72.  Thus, its aesthetic score is 54x72=3888.

农民约翰的奶牛最近收到了一大块大理石，不幸的是，它有许多缺陷.。为了描述这些，我们可以用n个正方形网格来表示一块大理石（5 < n = n = 300），其中字符“\*”表示一个不完美和“。

母牛想雕刻一个号码“8”在这一块大理石（牛很喜欢数字“8”，因为他们对他们的每一个四英尺，有偶蹄有效地数到8，用“脚”）。然而，奶牛需要你的帮助，以确定最佳放置在图八块大理石。这里有一些属性定义一个有效的数字八：

图八包括两个矩形，一个顶部和一个底部。顶部和底部至少有一个单元在其内部。顶部矩形的底部边缘是底部矩形顶部边缘的一个（不一定是适当的）子集.。

图八只能刻在大理石的无瑕疵区域。

图八的美学得分等于其两个矩形所包围的区域的乘积.。奶牛希望最大限度地提高这一成绩。

inputFormat:
\* Line 1: A single integer N, indicating the side length of the marble.

\* Lines 2..N+1: Each line describes a row of the marble, and contains N characters which are each either '\*' (an imperfection) or '.' (a flawless section).

第1行：一个整数n，表示大理石的边长。

行2 N + 1：每行描述了一排大理石，并包含n个字符，每个都是“\*”（缺陷）或'.' (完整)。

outputFormat: \* Line 1: The highest aesthetic score of any figure eight which doesn't use any imperfect squares of the marble.  If no figure eight is attainable, then output -1.

hint:
顶部的矩形面积6X9 = 54，和底部矩形面积12x6 = 72。因此，它的审美评分54x72 = 3888。

给出一个n×n的区域，其中有一些位置有瑕疵。现在要在没有瑕疵的位置中雕一个8”出来。

“8”字的定义为两个矩形框，框内面积均大于0，且一个矩形框的底边是是另一个矩形框的顶边的子集。

最大化两矩形框内面积的积。

感谢 @3505515693qq 提供翻译


title: [USACO13NOV] Farmer John has no Large Brown Cow S

description:
Farmer John likes to collect as many different types of cows as possible. In fact, he has collected almost every conceivable type of cow, except for a few, written on a short list of N lines (1 <= N <= 100).  The list looks like this:

Farmer John has no large brown noisy cow.

Farmer John has no small white silent cow.

Farmer John has no large spotted noisy cow.

Each item in the list describes a missing cow in terms of a short list of adjectives, and each item contains the same number of adjectives (3, in this case).  The number of adjectives per line will be in the range 2..30.

Farmer John has a cow fitting every other possible adjective combination not on his list.  In this example, the first adjective can be large or small, the second can be brown, white, or spotted, and the third can be noisy or silent.  This gives 2 x 3 x 2 = 12 different combinations, and Farmer John has a cow fitting each one, except for those specifically mentioned on his list.  In this example, a large, white, noisy cow is one of his 9 cows.  Farmer John is certain that he has at most 1,000,000,000 cows.

If Farmer John lists his cows in alphabetical order, what is the Kth cow in this list?

Partial credit opportunities: In the 10 test cases for this problem, cases 1..4 involve at most two adjectives per line in Farmer John's list.  In cases 1..6, each adjective will have exactly two possible settings (in all other cases, each adjective will have between 1 and N possible settings).

FJ喜欢收集不同的奶牛，他将未有的N(1 <= N <= 100)头奶牛用如下的形式描述：

Farmer John has no large brown noisy cow.

Farmer John has no small white silent cow.

Farmer John has no large spotted noisy cow.

每一行，描述一头FJ未有的牛。

每一行都含有相同个数的形容词，每行的形容词个数范围为2..30。

在以上给出的列表中，每行共有3个形容词，第一个形容词有两种（large和small），第二个形容词有3种（brown,white和spotted），第三个形容词有2种（noisy和silent）。

所以共可以组成12头不同的奶牛，除了列表给出的3头，他已经拥有了其他9头。FJ最多有1,000,000,000头牛。

若将FJ已经拥有的牛按形容词的字典序排序，请问他已有的第K头牛是哪一头。

inputFormat:
\* Line 1: Two integers, N and K.

\* Lines 2..1+N: Each line is a sentence like "Farmer John has no large spotted noisy cow.".  Each adjective in the sentence will be a string of at most 10 lowercase letters.  You know you have reached the end of the sentence when you see the string "cow." ending with a period.

outputFormat: \* Line 1: The description of the Kth cow on the farm.

samples:
3 7
Farmer John has no large brown noisy cow.
Farmer John has no small white silent cow.
Farmer John has no large spotted noisy cow.

hint:
The input matches the sample given in the problem statement above.  Farmer John would like to know the 7th cow on his farm, when listed in alphabetical order.

Farmer john has cows matching the following descriptions, listed in alphabetical order:

large brown silent

large spotted silent

large white noisy

large white silent

small brown noisy

small brown silent

small spotted noisy

small spotted silent

small white noisy

The 7th cow in this list is described as "small spotted noisy".


title: [USACO13NOV] Crowded Cows S

description:
Farmer John's N cows (1 <= N <= 50,000) are grazing along a one-dimensional fence.  Cow i is standing at location x(i) and has height h(i) (1 <= x(i),h(i) <= 1,000,000,000).

A cow feels "crowded" if there is another cow at least twice her height within distance D on her left, and also another cow at least twice her height within distance D on her right (1 <= D <= 1,000,000,000).  Since crowded cows produce less milk, Farmer John would like to count the number of such cows.  Please help him.

FJ有 $N(1\le N\le50000)$ 头奶牛沿着一维的栅栏吃草，第 $i$ 头奶牛在目标点 $x_i$ ，它的身高是 $h_i (1 \le x_i,h_i\le10^9)$。

当一头奶牛左边 $D(1\le D\le10^9)$ 距离内且右边 $D$ 距离内有身高至少是它的两倍的奶牛，它就会觉得拥挤。

请计算觉得拥挤的奶牛的数量。

inputFormat:
\* Line 1: Two integers, N and D.

\* Lines 2..1+N: Line i+1 contains the integers x(i) and h(i).  The locations of all N cows are distinct.

第一行两个整数 $N,D$。

接下来 $N$ ，每行两个整数 $x_i,h_i$。保证 $x_i$ 互不相同。

outputFormat:
\* Line 1: The number of crowded cows.

一行一个整数，表示觉得拥挤的奶牛的数量。

hint:
There are 6 cows, with a distance threshold of 4 for feeling crowded.  Cow #1 lives at position x=10 and has height h=3, and so on.

The cows at positions x=5 and x=6 are both crowded.


title: [USACO13NOV] Pogo-Cow S

description:
In an ill-conceived attempt to enhance the mobility of his prize cow Bessie, Farmer John has attached a pogo stick to each of Bessie's legs. Bessie can now hop around quickly throughout the farm, but she has not yet learned how to slow down.

To help train Bessie to hop with greater control, Farmer John sets up a practice course for her along a straight one-dimensional path across his farm.  At various distinct positions on the path, he places N targets on which Bessie should try to land (1 <= N <= 1000).  Target i is located at position x(i), and is worth p(i) points if Bessie lands on it.  Bessie starts at the location of any target of her choosing and is allowed to move in only one direction, hopping from target to target.  Each hop must cover at least as much distance as the previous hop, and must land on a target.

Bessie receives credit for every target she touches (including the initial target on which she starts).  Please compute the maximum number of points she can obtain.

FJ给奶牛贝西的脚安装上了弹簧，使它可以在农场里快速地跳跃，但是它还没有学会如何降低速度。

FJ觉得让贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了N (1 <= N <= 1000)个目标点，目标点i在目标点x(i)，该点得分为p(i)。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。

每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。

inputFormat:
\* Line 1: The integer N.

\* Lines 2..1+N: Line i+1 contains x(i) and p(i), each an integer in the range 0..1,000,000.

outputFormat: \* Line 1: The maximum number of points Bessie can receive.

hint:
There are 6 targets.  The first is at position x=5 and is worth 6 points, and so on.

Bessie hops from position x=4 (8 points) to position x=5 (6 points) to position x=7 (6 points) to position x=10 (5 points).


title: [USACO13NOV] Empty Stalls G

description:
Farmer John's new barn consists of a huge circle of N stalls (2 <= N <= 3,000,000), numbered 0..N-1, with stall N-1 being adjacent to stall 0.

At the end of each day, FJ's cows arrive back at the barn one by one, each with a preferred stall they would like to occupy.  However, if a cow's preferred stall is already occupied by another cow, she scans forward sequentially from this stall until she finds the first unoccupied stall, which she then claims.  If she scans past stall N-1, she continues scanning from stall 0.

Given the preferred stall of each cow, please determine the smallest index of a stall that remains unoccupied after all the cows have returned to the barn.  Notice that the answer to this question does not depend on the order in which the cows return to the barn.

In order to avoid issues with reading huge amounts of input, the input to this problem is specified in a concise format using K lines (1 <= K <= 10,000) each of the form:

X Y A B

One of these lines specifies the preferred stall for XY total cows: X cows prefer each of the stalls f(1) .. f(Y), where f(i) = (Ai + B) mod N.  The values of A and B lie in the range 0...1,000,000,000.

Do not forget the standard memory limit of 64MB for all problems.

约翰的谷仓中有N(2 <= N <=3,000,000)个房间，编号0到N-1，这些房间排布成环状,编号0的和编号N-1的相邻。

每天傍晚，奶牛们一只一只排队回到谷仓，每头奶牛都有一个喜欢的房间，但是，如果它喜欢的房间已被其他奶牛占了，它会向前挨个探索其他房间（如果它探索过了N-1号房间，它会继续探索0号房间，以此继续下去）直到探到第一个没有被占用的房间，这时它会宣布占用这个房间。

告诉你每头奶牛喜欢的房间，当所有奶牛都找到房间后，剩下的没被占用的房间中，编号最小的是哪个。很明显，问题的答案与奶牛进入谷仓的顺序无关。

为避免输入内容过多。本题的输入数据采用一种简洁的方式：一共K(1 <= K <=10,000)行，每行格式如下：

X Y A B

表示有Y批奶牛，每批X头，也就是总共X\*Y只奶牛喜欢的房间号。Y批奶牛编号1到Y，第i批X头奶牛喜欢的房间号为(A\*i+B) Mod N.

A和B的取值范围为0...1,000,000,000

注意，只有64M的空间。

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

\* Lines 2..1+K: Each line contains integers X Y A B, interpreted as above.  The total number of cows specified by all these lines will be at most N-1.  Cows can be added to the same stall by several of these lines.

outputFormat: \* Line 1: The minimum index of an unoccupied stall.

hint:
There are 10 stalls in the barn, numbered 0..9.  The second line of input states that 3 cows prefer stall (2\*1+4) mod 10 = 6, and 3 cows prefer stall (2\*2+4) mod 10 = 8.  The third line states that 2 cows prefer stall (0\*1+1) mod 10 = 1.  Line four specifies that 1 cow prefers stall (1\*1+7) mod 10 = 8 (so a total of 4 cows prefer this stall).

All stalls will end up occupied except stall 5.


title: [USACO13NOV] Line of Sight G

description:
Farmer John's N cows (1 <= N <= 50,000) are located at distinct points in his two-dimensional pasture.  In the middle of the pasture is a large circular grain silo.  Cows on opposite sides of the silo cannot see each-other, since the silo blocks their view.  Please determine the number of pairs of cows that can see each-other via a direct line of sight.

The grain silo is centered at the origin (0,0) and has radius R.  No cow is located on or inside the circle corresponding to the silo, and no two cows lie on a tangent line to the silo.  The value of R is in the range 1..1,000,000, and each cow lives at a point with integer coordinates in the range -1,000,000..+1,000,000.

给定平面上的 $N$ 个点，求有多少点对能互相看见而不被以原点为圆心，$R$ 为半径的圆挡住。

题目保证不存在圆上或圆内的点，也不存在连接两点的线段为圆的切线。

$1\le N\le50000$

$1\le R\le10^6$

$|x|,|y|\le10^6$

inputFormat:
\* Line 1: Two integers: N and R.

\* Lines 2..1+N: Each line contains two integers specifying the (x,y) coordinates of a cow.

outputFormat: \* Line 1: The number of pairs of cows who can see each-other.

hint:
There are 4 cows at positions (0,10), (0,-10), (10,0), and (-10,0).  The silo is centered at (0,0) and has radius 5.

All 6 pairs of cows can see each-other, except for the pairs situated on opposite sides of the silo: the cows at (-10,0) and (10,0) cannot see each-other, and the cows at (0,-10) and (0,10) cannot see each-other.


title: [USACO13NOV] No Change G

description:
Farmer John is at the market to purchase supplies for his farm.  He has in his pocket K coins (1 <= K <= 16), each with value in the range 1..100,000,000.  FJ would like to make a sequence of N purchases (1 <= N <= 100,000), where the ith purchase costs c(i) units of money (1 <= c(i) <= 10,000).  As he makes this sequence of purchases, he can periodically stop and pay, with a single coin, for all the purchases made since his last payment (of course, the single coin he uses must be large enough to pay for all of these).  Unfortunately, the vendors at the market are completely out of change, so whenever FJ uses a coin that is larger than the amount of money he owes, he sadly receives no changes in return!

Please compute the maximum amount of money FJ can end up with after making his N purchases in sequence.  Output -1 if it is impossible for FJ to make all of his purchases.

约翰到商场购物，他的钱包里有K(1 <= K <= 16)个硬币，面值的范围是1..100,000,000。

约翰想按顺序买 N个物品(1 <= N <= 100,000)，第i个物品需要花费c(i)块钱，(1 <= c(i) <= 10,000)。

在依次进行的购买N个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。

请计算出在购买完N个物品后，约翰最多剩下多少钱。如果无法完成购买，输出-1

inputFormat:
\* Line 1: Two integers, K and N.

\* Lines 2..1+K: Each line contains the amount of money of one of FJ's coins.

\* Lines 2+K..1+N+K: These N lines contain the costs of FJ's intended purchases.

outputFormat: \* Line 1: The maximum amount of money FJ can end up with, or -1 if FJ cannot complete all of his purchases.

hint:
FJ has 3 coins of values 12, 15, and 10.  He must make purchases in sequence of value 6, 3, 3, 2, 3, and 7.

FJ spends his 10-unit coin on the first two purchases, then the 15-unit coin on the remaining purchases.  This leaves him with the 12-unit coin.


title: [USACO13DEC] Milk Scheduling S

description:
Farmer John has N cows that need to be milked (1 <= N <= 10,000), each of which takes only one unit of time to milk.

Being impatient animals, some cows will refuse to be milked if Farmer John waits too long to milk them.  More specifically, cow i produces g\_i gallons of milk (1 <= g\_i <= 1000), but only if she is milked before a deadline at time d\_i (1 <= d\_i <= 10,000).  Time starts at t=0, so at most x total cows can be milked prior to a deadline at time t=x.

Please help Farmer John determine the maximum amount of milk that he can obtain if he milks the cows optimally.

FJ有N(1 <= N <= 10,000)头牛要挤牛奶，每头牛需要花费1单位时间。

奶牛很厌烦等待，奶牛i在它的截止时间d\_i (1 <= d\_i <= 10,000)前挤g(1 <= g\_i <= 1000)的奶，否则将不能挤奶。时间t开始时为0，即在时间t=x时，最多可以挤x头奶牛。

请计算FJ的最大挤奶量。

inputFormat:
\* Line 1: The value of N.

\* Lines 2..1+N: Line i+1 contains the integers g\_i and d\_i.

outputFormat: \* Line 1: The maximum number of gallons of milk Farmer John can obtain.

hint:
There are 4 cows.  The first produces 10 gallons of milk if milked by time 3, and so on.

Farmer John milks cow 3 first, giving up on cow 4 since she cannot be milked by her deadline due to the conflict with cow 3.  Farmer John then milks cows 1 and 2.


title: [USACO13DEC] Vacation Planning S

description:
有N(1 <= N <= 200)个农场，用1..N编号。航空公司计划在农场间建立航线。对于任意一条航线，选择农场1..K中的农场作为枢纽(1 <= K <= 100, K <= N)。

当前共有M (1 <= M <= 10,000)条单向航线连接这些农场，从农场u\_i 到农场 v\_i, 将花费 d\_i美元。(1 <= d\_i <= 1,000,000).

航空公司最近收到Q (1 <= Q <= 10,000)个单向航行请求。第i个航行请求是从农场a\_i到农场 b\_i，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。

请计算可行航行请求的数量，及完成所有可行请求的总费用。

inputFormat:
\* Line 1: Four integers: N, M, K, and Q.

\* Lines 2..1+M: Line i+1 contains u\_i, v\_i, and d\_i for flight i.

\* Lines 2+M..1+M+Q: Line 1+M+i describes the ith trip in terms of a\_i and b\_i

outputFormat:
\* Line 1: The number of trips (out of Q) for which a valid route is possible.

\* Line 2: The sum, over all trips for which a valid route is possible, of the minimum possible route cost.

hint:
There are three farms (numbered 1..3); farm 1 is a hub.  There is a $10 flight from farm 3 to farm 1, and so on.  We wish to look for trips from farm 3 to farm 2, from 2->3, and from 1->2.

The trip from 3->2 has only one possible route, of cost 10+7.  The trip from 2->3 has no valid route, since there is no flight leaving farm 2.  The trip from 1->2 has only one valid route again, of cost 7.


title: [USACO13DEC] The Bessie Shuffle S

description:
Bessie is practicing her card tricks.  She has already mastered the Bessie- shuffle -- a shuffle on M (2 <= M <= 100,000) cards that reorganizes the cards so the i-th card from the top is now the P[i]-th card from the top.

Now Bessie is practicing shuffles on larger decks.  She has a deck of N cards (M <= N <= 100,000) conveniently labeled 1 to N.  She shuffles this deck by taking the first M cards and performing the Bessie-shuffle on them, placing the shuffled cards back on top of the deck.  She then removes the top card from the deck and places it face down.  She repeats this process, placing the top cards successively on top of each other, until she is out of cards.  When Bessie has less than M cards left, she no longer performs the Bessie-shuffle, but continues to place the top card on top of the others.

Bessie knows that the deck initially started in sorted order, with 1 on top, 2 next, and N on the bottom.  Given the description of the Bessie-shuffle, help Bessie compute which cards end up located at Q different specified positions (1 <= Q <= N, Q <= 5,000) in the deck.

贝西有一种独门的洗牌方法，称为 A 类洗牌法；

A 类洗牌法的具体过程：将一堆共 $M$（$2 \le M \le 10 ^ 5$）张从上到下编号 $1, 2, \cdots, M$ 的纸牌，从上到下第 $i$ 张牌洗到位置 $p _ i$。

例如，$M=3，p = \{3, 1, 2\}$，则执行一次 A 类洗牌法后，从上到下将变为 $2, 3, 1$，即牌 $1$ 放到位置 $3$，牌 $2$ 放到位置 $1$，牌 $3$ 放到位置 $2$。

贝西现在要练习另外一种洗牌方法，称为 B 类洗牌法。

B 类洗牌法的具体过程：

有一堆 $N$（$M \le N \le 10 ^ 5$）张编号为 $1, 2, \cdots, N$ 的牌，并按从上到下 $1$ 到 $N$ 的顺序堆放。另有一个牌堆用来辅助洗牌，称为临时堆，开始时为空。

1. 将最上面 $M$ 张牌进行一次 A 类洗牌法；
2. 将最上面的一张牌放到临时堆的最上方；
3. 重复前两个操作，直到原先的堆没有牌为止。

以上过程中，当原先堆的牌不足 $M$ 张的时候，将不进行 A 类洗牌法，而是将最上面的牌依次放到临时堆上。

给定 $N, M$ 和排列 $p$。现在有 $Q$（$1 \le Q \le \min(N, 5000)$）个询问，请求出对其做一次 B 类洗牌法后临时堆中 $q _ i$ 位置上的牌的编号。

inputFormat:
\* Line 1: A single line containing N, M and Q separated by a space.

\* Lines 2..1+M: Line i+1 indicates the position from the top, P[i], of the i-th card in the Bessie-shuffle (1 <= P[i] <= M).

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

describing the i-th query.  You are to compute the label on the card located in position q\_i from the top (1 <= q\_i <= N).

outputFormat: \* Lines 1..Q: On the i-th line, print a single integer indicating the card at position q\_i from the top.

hint:
Bessie has a deck of 5 cards initially ordered as [1, 2, 3, 4, 5].  Her shuffle is on 3 cards and has the effect of moving the top card to the bottom.  There are 5 queries querying each position in the deck.

The shuffle proceeds as:

```cpp
[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (put 2 face down)
[3, 1, 4, 5] -> [1, 4, 3, 5] (put 1 face down)
[4, 3, 5] -> [3, 5, 4] (put 3 face down)
[5, 4] (put 5 face down)
[4] (put 4 face down)
```
This produces the final order of [4, 5, 3, 1, 2]


title: [USACO13DEC] Vacation Planning G

description:
Air Bovinia operates flights connecting the N farms that the cows live on (1 <= N <= 20,000). As with any airline, K of these farms have been designated as hubs (1 <= K <= 200, K <= N).

Currently, Air Bovinia offers M one-way flights (1 <= M <= 20,000), where flight i travels from farm u\_i to farm v\_i and costs d\_i (1 <= d\_i <= 10,000) dollars.  As with any other sensible airline, for each of these flights, at least one of u\_i and v\_i is a hub.  There is at most one direct flight between two farms in any given direction, and no flight starts and ends at the same farm.

Bessie is in charge of running the ticketing services for Air Bovinia. Unfortunately, while she was away chewing on delicious hay for a few hours, Q one-way travel requests for the cows' holiday vacations were received (1 <= Q <= 50,000), where the ith request is from farm a\_i to farm b\_i.

As Bessie is overwhelmed with the task of processing these tickets, please help her compute whether each ticket request can be fullfilled, and its minimum cost if it can be done.

To reduce the output size, you should only output the total number of ticket requests that are possible, and the minimum total cost for them. Note that this number might not fit into a 32-bit integer.

是n个点m条有向边，求两两之间的最短路，要求路径上必须经过编号1~k的至少一个点

inputFormat:
\* Line 1: The integers N, M, K, and Q.

\* Lines 2..M + 1: Line i+1 contains u\_i, v\_i, and d\_i. (1 <= u\_i, v\_i <= N, u\_i != v\_i)

\* Lines M + 2..M + K + 1: Each of these lines contains the ID of a single hub (in the range 1..N).

\* Lines M + K + 2..M + K + Q + 1: Two numbers per line, indicating a request for a ticket from farm a\_i to b\_i. (1 <= a\_i, b\_i <= N, a\_i != b\_i)

outputFormat:
\* Line 1: The number of ticket requests that can be fullfilled.

\* Line 2: The minimum total cost of fulling the possible ticket requests

translation:
有N($1 \le N \le
2\times 10^4$)个农场，用1…N编号。航空公司计划在农场间建立航线。对于任意一条航线，选择农场1…K中的农场作为枢纽($1 \le K \le
200 \le N$)。

当前共有 $M$($1 \le M \le 2\times 10^4$)条单向航线连接这些农场，从农场 $u_i$ 到农场 $v_i$, 将花费 $d_i$ 美元。($1 \le
d_i \le 10^4$).

航空公司最近收到 $Q$($1 \le Q \le 5\times 10^4$)个单向航行请求。第 $i$ 个航行请求是从农场 $a_i$ 到农场 $b_i$，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。

请计算可行航行请求的数量，及完成所有可行请求的总费用

hint: For the first flight, the only feasible route is 1->2->3, costing 20. There are no flights leaving farm 3, so the poor cows are stranded there.


title: [USACO13DEC] Optimal Milking G

description:
Farmer John has recently purchased a new barn containing N milking machines (1 <= N <= 40,000), conveniently numbered 1..N and arranged in a row.

Milking machine i is capable of extracting M(i) units of milk per day (1 <= M(i) <= 100,000).  Unfortunately, the machines were installed so close together that if a machine i is in use on a particular day, its two neighboring machines cannot be used that day (endpoint machines have only one neighbor, of course).  Farmer John is free to select different subsets of machines to operate on different days.

Farmer John is interested in computing the maximum amount of milk he can extract over a series of D days (1 <= D <= 50,000).  At the beginning of each day, he has enough time to perform maintenance on one selected milking machine i, thereby changing its daily milk output M(i) from that day forward. Given a list of these daily modifications, please tell Farmer John how much milk he can produce over D days (note that this number might not fit into a 32-bit integer).

FJ最近买了1个新仓库, 内含N 个挤奶机,1 到N 编号并排成一行。

挤奶机i 每天能产出M(i) 单位的奶。不幸的是, 机器装得太近以至于如果一台机器i 在某天被使用, 那与它相邻的两台机器那一天不能被使用

(当然, 两端点处的机器分别只有一个与之相邻的机器)。

FJ 可自由选择不同的机器在不同的日子工作。

FJ感兴趣于计算在D 天内他能产出奶的最大值。在每天开始时, 他有足够的时间维护一个选中的挤奶机i, 从而改变它从那天起的每日产奶量M(i)。

给出这些每日的修改,请告诉FJ他D 天中能产多少奶。

inputFormat:
\* Line 1: The values of N and D.

\* Lines 2..1+N: Line i+1 contains the initial value of M(i).

\* Lines 2+N..1+N+D: Line 1+N+d contains two integers i and m,

indicating that Farmer John updates the value of M(i) to m at the beginning of day d.

outputFormat: \* Line 1: The maximum total amount of milk FJ can produce over D days.

hint:
There are 5 machines, with initial milk outputs 1,2,3,4,5.  On day 1, machine 5 is updated to output 2 unit of milk, and so on.

On day one, the optimal amount of milk is 2+4 = 6 (also achievable as 1+3+2).  On day two, the optimal amount is 7+4 = 11.  On day three, the optimal amount is 10+3+2=15.

题意简述：给定n个点排成一排，每个点有一个点权，多次改变某个点的点权并将最大点独立集计入答案，输出最终的答案

感谢@zht467 提供翻译


title: [USACO13DEC] The Bessie Shuffle G

description:
Bessie is practicing her card tricks.  She has already mastered the Bessie- shuffle -- a shuffle on M (2 <= M <= 100,000) cards that reorganizes the cards so the i-th card from the top is now the P[i]-th card from the top.

Now Bessie is practicing shuffles on larger decks.  She has a deck of N cards (M <= N <= 1,000,000,000) conveniently labeled 1 to N.  She shuffles this deck by taking the first M cards and performing the Bessie-shuffle on them, placing the shuffled cards back on top of the deck.  She then removes the top card from the deck and places it face down.  She repeats this process, placing the top cards successively on top of each other, until she is out of cards.  When Bessie has less than M cards left, she no longer performs the Bessie-shuffle, but continues to place the top card on top of the others.

Bessie knows that the deck initially started in sorted order, with 1 on top, 2 next, and N on the bottom.  Given the description of the Bessie-shuffle, help Bessie compute which cards end up located at Q different specified positions (1 <= Q <= N, Q <= 5,000) in the deck.

50% of test cases will have N <= 100,000.

贝西有一种独门的洗牌方法，称为 A 类洗牌法；

A 类洗牌法的具体过程：将一堆共 $M$（$2 \le M \le 10 ^ 5$）张从上到下编号 $1, 2, \cdots, M$ 的纸牌，从上到下第 $i$ 张牌洗到位置 $p _ i$。

例如，$M=3，p = \{3, 1, 2\}$，则执行一次 A 类洗牌法后，从上到下将变为 $2, 3, 1$，即牌 $1$ 放到位置 $3$，牌 $2$ 放到位置 $1$，牌 $3$ 放到位置 $2$。

贝西现在要练习另外一种洗牌方法，称为 B 类洗牌法。

B 类洗牌法的具体过程：

有一堆 $N$（$M \le N \le 10 ^ 9$）张编号为 $1, 2, \cdots, N$ 的牌，并按从上到下 $1$ 到 $N$ 的顺序堆放。另有一个牌堆用来辅助洗牌，称为临时堆，开始时为空。

1. 将最上面 $M$ 张牌进行一次 A 类洗牌法；
2. 将最上面的一张牌放到临时堆的最上方；
3. 重复前两个操作，直到原先的堆没有牌为止。

以上过程中，当原先堆的牌不足 $M$ 张的时候，将不进行 A 类洗牌法，而是将最上面的牌依次放到临时堆上。

给定 $N, M$ 和排列 $p$。现在有 $Q$（$1 \le Q \le \min(N, 5000)$）个询问，请求出对其做一次 B 类洗牌法后临时堆中 $q _ i$ 位置上的牌的编号。

$50\%$ 的数据中，$N \le 10 ^ 5$。

hint:
Bessie has a deck of 5 cards initially ordered as [1, 2, 3, 4, 5].  Her shuffle is on 3 cards and has the effect of moving the top card to the bottom.  There are 5 queries querying each position in the deck.

The shuffle proceeds as:

```plain
[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (put 2 face down)
[3, 1, 4, 5] -> [1, 4, 3, 5] (put 1 face down)
[4, 3, 5] -> [3, 5, 4] (put 3 face down)
[5, 4] (put 5 face down)
[4] (put 4 face down)
```
This produces the final order of [4, 5, 3, 1, 2]

贝西的五张牌刚开始顺序为 [1, 2, 3, 4, 5]。她一次洗三张牌，效果是将第一张牌放到底部。以上五个问题询问了每一张牌的位置。

洗牌的顺序是:

```plain
[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (将2正面向下放置)
[3, 1, 4, 5] -> [1, 4, 3, 5] (将1正面向下放置)
[4, 3, 5] -> [3, 5, 4] (将3正面向下放置)
[5, 4] (将5正面向下放置)
[4] (将4正面向下放置)
```
这就形成了最终的顺序：[4, 5, 3, 1, 2]


title: [USACO14JAN] Cow Curling G

description:
Cow curling is a popular cold-weather sport played in the Moolympics.

Like regular curling, the sport involves two teams, each of which slides N heavy stones (3 <= N <= 50,000) across a sheet of ice.  At the end of the game, there are 2N stones on the ice, each located at a distinct 2D point.

Scoring in the cow version of curling is a bit curious, however.  A stone is said to be "captured" if it is contained inside a triangle whose corners are stones owned by the opponent (a stone on the boundary of such a triangle also counts as being captured).  The score for a team is the number of opponent stones that are captured.

Please help compute the final score of a cow curling match, given the locations of all 2N stones.

有两支队伍在比赛，一队可以一次取出3个点来，所围成的三角形覆盖的区域可以“捕获”对方的点，问两支队伍各能够捕获对方多少个点。

inputFormat:
\* Line 1: The integer N.

\* Lines 2..1+N: Each line contains 2 integers specifying the x and y coordinates of a stone for team A (each coordinate lies in the range -40,000 .. +40,000).

\* Lines 2+N..1+2N: Each line contains 2 integers specifying the x and y coordinates of a stone for team B (each coordinate lies in the range -40,000 .. +40,000).

outputFormat: \* Line 1: Two space-separated integers, giving the scores for teams A and B.

hint:
Each team owns 4 stones.  Team A has stones at (0,0), (0,2), (2,0), and (2,2), and team B has stones at (1,1), (1,10), (-10,3), and (10,3).

Team A captures their opponent's stone at (1,1).  Team B captures their opponent's stones at (0,2) and (2,2).


title: [USACO14JAN] Building a Ski Course G

description:
Farmer John is helping to turn his large field into a ski course for the upcoming winter Moolympics.  The field has dimensions M x N (1 <= M,N <= 100), and its intended final composition is described by an M x N grid of characters like this:

RSRSSS
RSRSSS
RSRSSS
Each character describes how the snow in a unit square of the field should be groomed: either 'R' for 'rough' or 'S' for 'smooth' (the Moolympics organizers think that a course is more interesting if it has a mixture of rough and smooth patches).

To build the desired course, Farmer John plans to modify his tractor so that it can stamp any B x B patch of the field (B <= M, B <= N) with either entirely smooth snow or entirely rough snow.  Since it takes a long time to reset the tractor between each of these stamps, FJ wants to make B as large as possible.  With B = 1, he can clearly create the desired ski course by stamping each individual square with either R or S, as intended.  However, for larger values of B, it may no longer be possible to create the desired course design.  Every unit square of the course must at some point be stamped by FJ's tractor; it cannot be left in its default state.

Please help FJ determine the largest possible value of B he can successfully use.

滑雪场的设计图是一个M\*NM x N (1 <= M,N <= 100)的矩阵，每个格子里用一个字母R（表示粗糙）或者S（表示平整）。

比如：

RSRSSS

RSRSSS

RSRSSS

农民约翰的拖拉机每次可以将一块B\*B (B <= M, B <= N)的区域全部标记B\*B (B <= M, B <= N)的R或者S，他希望B能够尽量地大。一个格子可以被多次标记，下一次标记能够覆盖前一次标记，每个格子可以都至少被标记一次。

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

\* Lines 2..M+1: M lines of exactly N characters (each R or S), describing the desired ski course design.

outputFormat: \* Line 1: The maximum value of B Farmer John can use to create the desired course pattern.

hint: FJ can stamp a rough patch spanning columns 1-3, followed by a smooth patch spanning columns 2-4, then a rough patch spanning columns 3-5, and finally a smooth patch spanning columns 4-6.


title: [USACO14JAN] Ski Course Rating G

description:
The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 <= M,N <= 500), each elevation being in the range 0 .. 1,000,000,000.

Some of the cells in this grid are designated as starting points for the course.  The organizers of the Moolympics want to assign a difficulty rating to each starting point.  The difficulty level of a starting point P should be the minimum possible value of D such that a cow can successfully reach at least T total cells of the grid (1 <= T <= MN), if she starts at P and can only move from cell to adjacent cell if the absolute difference in elevation between the cells is at most D.  Two cells are adjacent if one is directly north, south, east, or west of the other.

Please help the organizers compute the difficulty rating for each starting point.

滑雪场用一个M\*N(1 <= M,N <= 500)的数字矩阵表示海拔高度，每个数字表示一个范围在0 .. 1,000,000,000的高度。有些格子被指定为起点，组织者想对这些起点做难度评级。

如果起点P点是一个难度级别为D的起点，则D必须是满足以下条件的一个最小值：

（1）从一个格子只能滑到相邻的格子；

（2）这两个格子的海拔差不超过D；

（3）至少能够到达T（1 <= T <= M\*N）个格子（包括起点本身）。

inputFormat:
\* Line 1: The integers M, N, and T.

\* Lines 2..1+M: Each of these M lines contains N integer elevations.

\* Lines 2+M..1+2M: Each of these M lines contains N values that are either 0 or 1, with 1 indicating a cell that is a starting point.

outputFormat: \* Line 1: The sum of difficulty ratings of all starting points (note that this may not fit into a 32-bit integer, even though individual difficulty ratings will).

hint:
The ski course is described by a 3 x 5 grid of elevations.  The upper-left and lower-right cells are designated as starting points.  From each starting point, we must be able to reach at least 10 cells.

The difficulty rating of the upper-left starting point is 4, and for the lower-right it is 20.


title: [USACO14FEB] Secret Code S

description:
Farmer John has secret message that he wants to hide from his cows; the message is a string of length at least 2 containing only the characters A..Z.

To encrypt his message, FJ applies a sequence of "operations" to it, where an operation applied to a string S first shortens S by removing either some (but not all) of the initial characters or some (but not all) of the final characters from S, after which the original string S is attached either at the beginning or end.  For example, a single operation to the string ABC could result in eight possible strings:

AABC
ABABC
BCABC
CABC
ABCA
ABCAB
ABCBC
ABCC
Given the final encrypted string, please count the number of possible ways FJ could have produced this string using one or more repeated operations applied to some source string.  Operations are treated as being distinct even if they give the same encryption of FJ's message.  For example, there are four distinct separate ways to obtain AAA from AA.

Print your answer out modulo 2014.

农民约翰收到一条的消息，记该消息为长度至少为2，只由大写字母组成的字符串S，他通过一系列操作对S进行加密。

他的操作为，删除S的前面或者后面的若干个字符（但不删光整个S），并将剩下的部分连接到原字符串S的前面或者后面。如对于S=‘ABC’，共有8总可能的操作结果：

AABC

ABABC

BCABC

CABC

ABCA

ABCAB

ABCBC

ABCC

给出加密后的目标字符串，请计算共有多少种加密的方案。

对于同字符的字符串，加密方案不止一种，比如把AA加密成AAA，共有4种加密方案。将你的答案mod 2014后输出。

inputFormat: \* Line 1: A single encrypted string of length at most 100.

outputFormat: \* Line 1: The number of ways FJ could have produced this string with one or more successive operations applied to some initial string of length at least 2, written out modulo 2014.  If there are no such ways, output zero.

hint:
Here are the different ways FJ could have produced ABABA:

1. Start with ABA -> AB+ABA

2. Start with ABA -> ABA+BA

3. Start with AB -> AB+A -> AB+ABA

4. Start with AB -> AB+A -> ABA+BA

5. Start with BA -> A+BA -> AB+ABA

6. Start with BA -> A+BA -> ABA+BA

7. Start with ABAB -> ABAB+A

8. Start with BABA -> A+BABA


title: [USACO14FEB] Airplane Boarding G

description:
FJ's cows have decided to take a vacation, and have miraculously managed to find an airline willing to sell them tickets.  When they arrive at the airport and start boarding their plane, they face an interesting problem, however.

The airplane has N seats, which we model as the points x=1 through x=N on the number line.  All N cows (1 <= N <= 200,000) are standing in line waiting to get to their seats.  Cow N is at position x=0, Cow N-1 is at position x=-1, and so on.  Cow i has been assigned to Seat S\_i, where S\_1,...,S\_N is a permutation of 1,...,N.

At each time step, each cow takes a step to the right if she can. When cow i reaches her seat S\_i, she will stop to put her baggage in the overhead bin, which takes T\_i seconds, and then sit down. For those T\_i steps, the cow behind her (if there is one) is blocked from moving forward.  If there is a line of cows behind her, the line is effectively blocked as well.

How long will it take for all the cows to sit down?

The sum of T\_i for all cows will be less than 1,000,000,000.

想象一下飞机有N个座位，N个座位相当于数轴上的1至N共N个整点，第1个座位在整点1处，第2个座位在整点2处，……第N个座位在整点N处。

有N个奶牛排好队，要登陆坐飞机，第N头奶牛在数轴的整点0处，第N−1头奶牛在数轴的整点−1处，……第1头奶牛在数轴的整点−N+1处。第i头奶牛的座位号是Si。注意：每头奶牛都有唯一的一个座位，不会出现多头奶牛有相同的座位号。

在每一秒钟，奶牛会向右移动一步到达下一个整点，前提是没有奶牛挡住它。 当第i头奶牛到达它的座位Si时，它需要花费Ti秒去把行李放到头顶的行李架上，然后坐到自己的位置上，在此过程中，由于飞机通道很窄，所以在第i头奶牛坐到自己座位之前，在它左边的所有奶牛都不能动，要等奶牛i放好行李坐好后才能动。

现在的问题是，至少要多少秒之后，所有的奶牛都能做到自己的座位上？

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

\* Lines 2..N+1: Two space-separated integers, S\_i and T\_i.

outputFormat: \* Line 1: A single line indicating the amount of time it takes to seat all cows.

hint:
Initially, the cows are situated like this:

cows -> 123

123 <- seats

with cow 1 trying to get to seat 2, cow 2 trying to get to seat 3, and cow 3 trying to get to seat 1.

After one step, they will all move 1 to the right and cow 3 will reach her seat:

123
123
Cow 3 takes 5 seconds to sit down, at which point she effectively disappears.

12
123
It takes 3 more seconds for cows 1 and 2 to reach their desired seats:

12
123
It takes 5 seconds for cow 1 to sit down and 10 seconds for cow 2 to sit down, so that's 10 seconds total.

In total this took 1 + 5 + 3 + 10 = 19 seconds.


title: [USACO14MAR] Counting Friends G

description:
Farmer John's N cows (2 <= N <= 500) have joined the social network "MooBook".

Each cow has one or more friends with whom they interact on MooBook.  Just for fun, Farmer John makes a list of the number of friends for each of his cows, but during the process of writing the list he becomes distracted, and he includes one extra number by mistake (so his list contains N+1 numbers, instead of N numbers as he intended).

Please help Farmer John figure out which numbers on his list could have been the erroneous extra number.

FJ又有n(1<=n<=500)头奶牛都有一个或一个以上的朋友。FJ记录每头牛的朋友数，但他傻不小心混入了一个错的数字，请找出。

inputFormat:
\* Line 1: The integer N.

\* Lines 2..2+N: Line i+1 contains the number of friends for one of FJ's cows, or possibly the extra erroneous number.

outputFormat:
\* Line 1: An integer K giving the number of entries in FJ's list that could be the extra number (or, K=0 means that there is no number on the list whose removal yields a feasible pairing of friends).

\* Lines 2..1+K: Each line contains the index (1..N+1) within the input ordering of a number of FJ's list that could potentially be the extra number -- that is, a number that can be removed such that the remaining N numbers admit a feasible set of

friendships among the cows.  These lines should be in sorted order.

hint:
Farmer John has 4 cows.  Two cows have only 1 friend each, two cows have 2 friends each, and 1 cow has 3 friends (of course, one of these numbers is extra and does not belong on the list).

Removal of the first number in FJ's list (the number 1) gives a remaining list of 2,2,1,3, which does lead to a feasible friendship pairing -- for example, if we name the cows A..D, then the pairings (A,B), (A,C), (A,D), and (B,C) suffice, since A has 3 friends, B and C have 2 friends, and D has 1 friend.  Similarly, removing the other "1" from FJ's list also works, and so does removing the "3" from FJ's list.  Removal of either "2" from FJ's list does not work -- we can see this by the fact that the sum of the remaining numbers is odd, which clearly prohibits us from finding a feasible pairing.


title: [USACO14OPEN] Fair Photography S

description:
FJ's N cows (2 <= N <= 100,000) are standing at various positions along a long one-dimensional fence.  The ith cow is standing at position x\_i (an integer in the range 0...1,000,000,000) and is either a plain white cow or a spotted cow.  No two cows occupy the same position, and there is at least one white cow.

FJ wants to take a photo of a contiguous interval of cows for the county fair, but in fairness to his different cows, he wants to ensure there are equal numbers of white and spotted cows in the photo.  FJ wants to determine the maximum size of such a fair photo, where the size of a photo is the difference between the maximum and minimum positions of the cows in the photo.

To give himself an even better chance of taking a larger photo, FJ has with him a bucket of paint that he can use to paint spots on an arbitrary subset of his white cows of his choosing, effectively turning them into spotted cows.  Please determine the largest size of a fair photo FJ can take, given that FJ has the option of painting some of his white cows (of course, he does not need to paint any of the white cows if he decides this is better).

inputFormat:
\* Line 1: The integer N.

\* Lines 2..1+N: Line i+1 contains x\_i and either W (for a white cow) or S (for a spotted cow).

outputFormat: \* Line 1: The maximum size of a fair photo FJ can take, after possibly painting some of his white cows to make them spotted.

translation:
在数轴上有  $N$  头牛，第  $i$  头牛位于  $x_i\:(0\le x_i\le 10^9)$ 。没有两头牛位于同一位置。
有两种牛：白牛和花斑牛。保证至少有一头白牛。你可以把白牛涂成花斑牛，不限数量，不限哪只。
找一段尽量长的区间，使得区间的两端点均有一头牛，且区间中白牛与花斑牛的数量相等。试求区间长度。

感谢 @Planet6174  的翻译

hint:
There are 5 cows.  One of them is a white cow at position 8, and so on.

FJ takes a photo of the cows from positions 3 to positions 10.  There are 4 cows in this range -- 3 white and 1 spotted -- so he needs to paint one of the white cows to make it spotted.


title: [USACO14OPEN] Dueling GPSs S

description:
Farmer John has recently purchased a new car online, but in his haste he accidentally clicked the "Submit" button twice when selecting extra features for the car, and as a result the car ended up equipped with two GPS navigation systems!  Even worse, the two systems often make conflicting decisions about the route that FJ should take.

The map of the region in which FJ lives consists of N intersections (2 <= N <= 10,000) and M directional roads (1 <= M <= 50,000).  Road i connects intersections A\_i (1 <= A\_i <= N) and B\_i (1 <= B\_i <= N). Multiple roads could connect the same pair of intersections, and a bi-directional road (one permitting two-way travel) is represented by two separate directional roads in opposite orientations.  FJ's house is located at intersection 1, and his farm is located at intersection N.  It is possible to reach the farm from his house by traveling along a series of directional roads.

Both GPS units are using the same underlying map as described above; however, they have different notions for the travel time along each road. Road i takes P\_i units of time to traverse according to the first GPS unit, and Q\_i units of time to traverse according to the second unit (each travel time is an integer in the range 1..100,000).

FJ wants to travel from his house to the farm.  However, each GPS unit complains loudly any time FJ follows a road (say, from intersection X to intersection Y) that the GPS unit believes not to be part of a shortest route from X to the farm (it is even possible that both GPS units can complain, if FJ takes a road that neither unit likes).

Please help FJ determine the minimum possible number of total complaints he can receive if he chooses his route appropriately.  If both GPS units complain when FJ follows a road, this counts as +2 towards the total.

inputFormat:
\* Line 1: The integers N and M.

Line i describes road i with four integers: A\_i B\_i P\_i Q\_i.

outputFormat: \* Line 1: The minimum total number of complaints FJ can receive if he routes himself from his house to the farm optimally.

translation:
Farmer John 最近在网上购买了一台新车，然而当他给这台新车挑选额外设备时他不小心快速地点击了“提交” 按钮两次，因此这台新车配备了两台 GPS 导航系统！更糟糕的是，两台系统对 Farmer John 的出行路线经常做出相互冲突的决定。

Farmer John 居住的区域包含 $N$ 个结点（$2 \le N \le 10000$）和 $M$ 条有向道路（$1 \le M \le 50000$）。第 $i$ 条道路从 $A_i$ 连向 $B_i$（$1 \le A_i, B_i \le N$）。多条道路可能连接同样一对结点，而一条双向道路是由两条单独的反向的道路来表示的。 Farmer John 的家在结点 $1$，他的农场在结点 $N$。数据保证从家出发经过一系列有向道路可以到达农场。

两台 GPS 系统的内置地图都如上所描述。然而，它们对通过每条道路所需时间的预计是不同的。第一台和第二台 GPS 系统预测通过道路 $i$ 需要花费的时间分别为 $P_i$ 和 $Q_i$ 个单位时间（通过每条道路所需时间是一个在 $[1, 10^5]$ 内的整数）。

Farmer John 想要从他的家去往农场。然而，当 Farmer John 通过了一条道路（假设是从 $X$ 到 $Y$），而一台 GPS 系统认为这条道路不是从 $X$ 前往农场的最短路径中的一部分时，这台 GPS 系统就会大声抱怨（如果两台 GPS 系统都认为该条道路都不是最短路径的一部分时，两台系统会同时抱怨）。

请帮助 Farmer John 求出，如果 Farmer John 合理地选择出行路线，两台 GPS 系统抱怨次数总和的最小值。如果 Farmer John 通过了一条路时两台 GPS 系统同时抱怨，那么抱怨次数增加 $2$。

hint:
There are 5 intersections and 7 directional roads.  The first road connects from intersection 3 to intersection 4; the first GPS thinks this road takes 7 units of time to traverse, and the second GPS thinks it takes 1 unit of time, etc.

If FJ follows the path 1 -> 2 -> 4 -> 5, then the first GPS complains on the 1 -> 2 road (it would prefer the 1 -> 3 road instead).  However, for the rest of the route 2 -> 4 -> 5, both GPSs are happy, since this is a shortest route from 2 to 5 according to each GPS.


title: [USACO14OPEN] Odometer S

description:
Farmer John's cows are on a road trip!  The odometer on their car displays an integer mileage value, starting at X (100 <= X <= 10^18) miles at the beginning of their trip and ending at Y (X <= Y <= 10^18) miles at the end of their trip.  Whenever the odometer displays an 'interesting' number (including at the start and end of the trip) the cows will moo.  A number is 'interesting' if when you look at all its digits except for leading zeros, at least half of these should be the same.  For example, the numbers 3223 and 110 are interesting, while the numbers 97791 and 123 are not.

Help FJ count how many times the cows will moo during the trip.

inputFormat: \* Line 1: The first line will contain two integers, X and Y, separated by a space.

outputFormat: \* Line 1: A single integer containing how many times the cows will moo during the trip.

translation:
农民约翰的牛正开始一个美妙的旅程。牛车的里程表上显示一个整数表示里程，旅程开始时里程数为 $X(100\le X\le 10^{18})$，结束时里程数为 $Y(X\le Y\le 10^{18})$。每当里程表显示一个有趣的数时（包括起点和终点数），牛们会发出愉快的叫声。

对于一个里程数的每一位，如果有至少一半的数字时相同的，则这个里程数一个有趣的数。例如：$3223$ 和 $110$ 是有趣的数，而 $97791$ 和 $123$ 则不是。

请计算，整个旅程中，牛们会发出多少吃愉快的叫声。

hint:
The trip starts with the odometer at 110 and ends at 133.

The cows moo when the odometer reads 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 131, and 133.


title: [USACO14OPEN] Cow Optics G

background: 征求翻译。如果你能提供翻译或者题意简述，请直接发讨论，感谢你的贡献。

description:
Farmer John's cows would like to host a dance party in their barn, complete with a laser light show.  Unfortunately, the only working laser they have found is located far away from the barn and too heavy to move, so they plan to re-direct the laser light to the barn using a series of mirrors.

The layout of the farm has the laser at position (0,0) pointing north (in the positive y direction), and the barn at (Bx, By); we can think of both the laser and the barn as points in the 2D plane.  There are already N cows (1 <= N <= 100,000) scattered throughout the farm holding mirrors that are aligned at angles of 45 degrees to the axes.  For example, a mirror aligned like \ will take a beam of light entering from below and reflect it to the left.  We can also think of the mirrors as being located at points in the 2D plane.

Just before pressing the big red button to activate the laser, Bessie noticed a major flaw in the plan: the laser cannot hit the barn with the mirrors in their current configuration!  As a result, she plans to run out onto the field, and hold up one more mirror (placed once again at a 45 degree angle) in order to redirect the laser onto the barn. Please count the number of locations in the field where Bessie can stand to accomplish this goal.

All coordinates are integers between -1,000,000,000 and 1,000,000,000. It is guaranteed that any mirrors to be placed will be in this range as well. The cows running the laser insist that the beam should never come back to (0,0) after leaving this location (and with the mirrors in their initial configuration, it is guaranteed that this will not happen).  No two cows occupy the same point in space, and Bessie cannot locate herself at the same position as an existing cow.

农场主约翰的牛想在谷仓里面举办舞会，用激光灯来表演。但不幸的是唯一的激光灯离谷仓太远，并且搬不动，所以牛们想用镜子来反射激光，使得激光照到谷仓。

激光的位置在（0,0），指向为北方（即y轴正方向），谷仓在位置（Bx，By）。已经有N头奶牛拿着镜子分散在农场的各个位置（1 <= N <= 100,000），镜子与原点之间的夹角为45度。例如一个这样（“\“）的镜子可以把从下方射来的光线反射成向左的光线。

Bessie在启动激光的前一刻意识到计划有缺陷，所以她自己又拿着一面镜子出去了，恰好使得激光照到谷仓。

请计算Bessie可能站在的位置的总数。

坐标范围：-1,000,000,000 到 1,000,000,000，数据保证初始时激光光束不会反射回（0,0）位置。同一点上不可能有多头牛，Bessie不能站在其他牛的位置。

inputFormat:
\* Line 1: The integers N, Bx, and By.

\* Lines 2..N + 1: Line i+1 describes the ith mirror with 3 elements: its (x,y) location, and its orientation (either '\' or '/').

第一行：三个整数：N，Bx，By。

第2~N+1行：每行两个整数表示牛的位置，一个字符（”/“或"\"）表示镜子怎么放置的。

outputFormat:
where Bessie can stand to redirect the laser to the barn.

Bessie所有可能站在的位置总数。

hint:
A mirror at (0,1) or (0,2) placed in either direction would do the trick.

样例中Bessie可能站在（0,1）或者（0,2）。

感谢@SystemLLH  提供翻译


title: [USACO14OPEN] Code Breaking G

description:
The cows keep getting in trouble by taking rides on Farmer John's tractor, so he has hidden the keys to the tractor in a fancy new safe in his office. Undeterred, the cows have vowed to try and break into this safe.

The safe is protected by a rather complicated passcode system. The passcode entry system is arranged as a rooted tree of N (1 <= N <= 20,000) nodes, each of which requires a digit between 0 and 9. The nodes are indexed 0..N-1.

The only information that the cows have is that certain sequences of length 5 do not occur along particular paths upwards through the tree.

For instance, suppose the tree is the following (rooted at A):

A <- B <- C <- D <- E

^
|
F
The cows might know that the sequence 01234 does not occur starting at F, and that the sequence 91234 does not occur starting at E. This information rules out 19 possible passcodes: all those of the form

4 <- 3 <- 2 <- 1 <- \*

^
|
0
or
4 <- 3 <- 2 <- 1 <- 9

^
|
\*
which gives 19 once we account for the fact that

4 <- 3 <- 2 <- 1 <- 9

^
|
0
appears twice.

Given M (1 <= M <= 50,000) length-5 sequences, together with their starting nodes in the tree, help the cows figure out how many passcodes have been ruled out. You should compute your answer modulo 1234567.

有一棵N个节点的有根树,每个节点可以填0~9.

有M个事实,就是从X开始往祖先一直跑的的包含X的5个节点(保证X上面一定存在这样一条路径,也就是说X的深度至少为5),一定不是ABCDE.(0<=A,B,C,D,E<=9)

求,根据这M个事实,共有多少种给这棵树全部填上数的方案一定是不可能的.

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

\* Lines 2..N: Line i+1 contains a single integer p(i), denoting the parent of node i in the tree (0 <= p(i) < i).

\* Lines N+1..N+M: Line N+i describes the ith sequence known not to occur in the code.  The line will contain v(i) and s(i) separated by a space, where v(i) is the starting node of the sequence, and s(i) is a 5-digit string known not to occur starting at v(i) and proceeding upward in the tree.  It is guaranteed that the root is at least 4 steps upward from v(i).

outputFormat:
\* Line 1: A single integer giving the number of ruled-out

configurations, modulo 1234567.


title: [USACO14DEC] Piggy Back S

description:
Bessie and her sister Elsie graze in different fields during the day, and in the evening they both want to walk back to the barn to rest. Being clever bovines, they come up with a plan to minimize the total amount of energy they both spend while walking.

Bessie spends B units of energy when walking from a field to an adjacent field, and Elsie spends E units of energy when she walks to an adjacent field.  However, if Bessie and Elsie are together in the same field, Bessie can carry Elsie on her shoulders and both can move to an adjacent field while spending only P units of energy (where P might be considerably less than B+E, the amount Bessie and Elsie would have spent individually walking to the adjacent field).  If P is very small, the most energy-efficient solution may involve Bessie and Elsie traveling to a common meeting field, then traveling together piggyback for the rest of the journey to the barn.  Of course, if P is large, it may still make the most sense for Bessie and Elsie to travel

separately.  On a side note, Bessie and Elsie are both unhappy with the term "piggyback", as they don't see why the pigs on the farm should deserve all the credit for this remarkable form of

transportation.

Given B, E, and P, as well as the layout of the farm, please compute the minimum amount of energy required for Bessie and Elsie to reach the barn.

inputFormat:
INPUT: (file piggyback.in)

The first line of input contains the positive integers B, E, P, N, and M.  All of these are at most 40,000.  B, E, and P are described above. N is the number of fields in the farm (numbered 1..N, where N >= 3), and M is the number of connections between fields.  Bessie and Elsie start in fields 1 and 2, respectively.  The barn resides in field N.

The next M lines in the input each describe a connection between a pair of different fields, specified by the integer indices of the two fields.  Connections are bi-directional.  It is always possible to travel from field 1 to field N, and field 2 to field N, along a series of such connections.

outputFormat:
OUTPUT: (file piggyback.out)

A single integer specifying the minimum amount of energy Bessie and

Elsie collectively need to spend to reach the barn.  In the example

shown here, Bessie travels from 1 to 4 and Elsie travels from 2 to 3

to 4.  Then, they travel together from 4 to 7 to 8.

translation:
Bessie 和 Elsie 在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie 要花费 $B$ 单位的能量，Elsie要花费 $E$ 单位的能量。

如果某次他们两走到同一个区域，Bessie 可以背着 Elsie 走路，花费 $P$ 单位的能量走到另外一个相连的区域。当然，存在 $P>B+E$ 的情况。

相遇后，他们可以一直背着走，也可以独立分开。

Bessie 从 $1$ 号区域出发，Elsie 从 $2$ 号区域出发，两个人都要返回到位于 $n$ 号区域的谷仓。

### 输入格式

第一行输入 5 个整数 $B,E,P,n,m$。$B,E,P$ 的含义如上文所述。
$n$ 表示农场中区域的数量，$m$ 表示连接两个区域的道路的数量。

接下来 $m$ 行，每行两个整数 $x,y$，描述一条 $x$ 区域和 $y$ 区域之间的双向边。数据保证图是连通的。

### 输出格式

一行一个整数，表示 Bessie 和 Elsie 能量花费总和的最小值。

### 数据范围

$1 \leq B,E,P,n,m \leq 4 \times 10^4$。

#### 样例解释：
Bessie 从 1 走到 4，Elsie 从 2 走到 3 再走到 4。然后，两个人一起从 4 走到 7，再走到 8。


title: [USACO14DEC] Cow Jog S

description:
The cows are out exercising their hooves again!  There are N cows

jogging on an infinitely-long single-lane track (1 <= N <= 100,000).

Each cow starts at a distinct position on the track, and some cows jog

at different speeds.

With only one lane in the track, cows cannot pass each other.  When a

faster cow catches up to another cow, she has to slow down to avoid

running into the other cow, becoming part of the same running group.

The cows will run for T minutes (1 <= T <= 1,000,000,000).  Please

help Farmer John determine how many groups will be left at this time.

Two cows should be considered part of the same group if they are at

the same position at the end of T minutes.

有N (1 <= N <= 100,000)头奶牛在一个单人的超长跑道上慢跑，每头牛的起点位置都不同。由于是单人跑道，所有他们之间不能相互超越。当一头速度快的奶牛追上另外一头奶牛的时候，他必须降速成同等速度。我们把这些跑走同一个位置而且同等速度的牛看成一个小组。

请计算T (1 <= T <= 1,000,000,000)时间后，奶牛们将分为多少小组。

inputFormat:
INPUT: (file cowjog.in)

The first line of input contains the two integers N and T.

The following N lines each contain the initial position and speed of a

single cow.  Position is a nonnegative integer and speed is a positive

integer; both numbers are at most 1 billion.  All cows start at

distinct positions, and these will be given in increasing order in

the input.

outputFormat:
OUTPUT: (file cowjog.out)

A single integer indicating how many groups remain after T minutes.


title: [USACO14DEC] Guard Mark G

description:
 Farmer John and his herd are playing frisbee.  Bessie throws thefrisbee down the field, but it's going straight to Mark the field handon the other team!  Mark has height H (1 <= H <= 1,000,000,000), butthere are N cows on Bessie's team gathered around Mark (2 <= N <= 20).They can only catch the frisbee if they can stack up to be at least ashigh as Mark.  Each of the N cows has a height, weight, and strength.A cow's strength indicates the maximum amount of total weight of thecows that can be stacked above her.

 Given these constraints, Bessie wants to know if it is possible forher team to build a tall enough stack to catch the frisbee, and if so,what is the maximum safety factor of such a stack.  The safety factorof a stack is the amount of weight that can be added to the top of thestack without exceeding any cow's strength.

inputFormat:
INPUT: (file guard.in)

The first line of input contains N and H.

The next N lines of input each describe a cow, giving its height,weight, and strength.  All are positive integers at most 1 billion.

outputFormat:
OUTPUT: (file guard.out)

 If Bessie's team can build a stack tall enough to catch the frisbee, please output the maximum achievable safety factor for such a stack.

Otherwise output "Mark is too tall" (without the quotes).

translation:
FJ将飞盘抛向身高为H(1 <= H <= 1,000,000,000)的Mark，但是Mark被N(2 <= N <= 20)头牛包围。牛们可以叠成一个牛塔，如果叠好后的高度大于或者等于Mark的高度，那牛们将抢到飞盘。

每头牛都一个身高，体重和耐力值三个指标。耐力指的是一头牛最大能承受的叠在他上方的牛的重量和。请计算牛们是否能够抢到飞盘。若是可以，请计算牛塔的最大稳定强度，稳定强度是指，在每头牛的耐力都可以承受的前提下，还能够在牛塔最上方添加的最大重量。


title: [USACO14DEC] Marathon G

background:
作为一名狂热的马拉松长跑运动员，贝茜喜欢为她的同伴们开设马拉松课程。她最近设计了一个有N个检查点的路线(1 < = N < = 100,000)，必须按顺序经过。

不幸的是，贝茜意识到其他的奶牛可能没有足够的耐力跑完全程。因此，她想知道特定的子路线需要多长时间才能跑完，其中的子路线是从完整路线的检查点中截取的的连续子序列。让事情变得更复杂的是，贝西知道其他的牛十分懒惰，可能会选择在任何时候跳过一个检查点——无论哪一种方法都能在最短的时间内完成。然而，他们不允许在子路线中跳过第一个或最后一个检查点。

为了建造最好的马拉松赛道，贝茜想要研究一下在她目前的课程中对检查点位置做出改变后可能造成的后果。请帮助她确定检查点位置的哪些更改将会影响运行不同子路线所需的时间(考虑到奶牛可能会选择在子路线跑步时忽略一个检查点)。

由于该课程设置在市中心的街道网络中，两个检查点之间的距离(x1,y1)和(x2,y2)是由| x1 - x2 | + | y1 - y2 |得出的。

description:
An avid marathon runner herself, Bessie enjoys creating marathon courses for her fellow cows to run.  She has most recently designed a route specified by N checkpoints (1 <= N <= 100,000) that must be visited in sequence.

Unfortunately, Bessie realizes that the other cows may not have the stamina to run the full route. She therefore wants to know how long certain sub-routes take to run, where a sub-route is a contiguous subsequence of the checkpoints from the full route.  To make matters more complicated, Bessie knows that the other cows, being lazy, might choose to skip one checkpoint any time they run a sub-route -- whichever one results in a minimum total travel time.  They are not allowed to skip the first or last checkpoints in a sub-route, however.

In order to build the best possible marathon course, Bessie wants to investigate the ramifications of making changes to the checkpoint locations in her current course.  Please help her determine how certain changes to checkpoint locations will affect the time required to run different sub-routes (taking into account that the cows might choose to omit one checkpoint any time they run a sub-route).

Since the course is set in a downtown area with a grid of streets, the distance between two checkpoints at locations (x1, y1) and (x2, y2) is given by |x1-x2| + |y1-y2|.

inputFormat:
INPUT: (file marathon.in)

The first line gives N and Q (1 <= Q <= 100,000).

The next N lines contain (x, y) locations of N checkpoints in the

sequence they must be visited along the route.  All coordinates are in the range -1000 .. 1000.

The next Q lines consist of updates and queries, one per line, to be processed in the order they are given. Lines will either take the form "U I X Y" or "Q I J".  A line of the form "U I X Y" indicates that the location of checkpoint I (1 <= I <= N) is to be changed to location (X, Y).  A line of the form "Q I J" asks for the minimum travel time of the sub-route from checkpoint I to checkpoint J (I <= J), given that the cows choose to skip one checkpoint along this sub-route (but not the endpoints I and J).

outputFormat:
OUTPUT: (file marathon.out)

For each sub-route length request, output on a single line the desired length.


title: [USACO15JAN] Stampede S

description:
Farmer John's N cows (1 <= N <= 50,000) appear to be stampeding along the road at the front of FJ's farm, but they are actually just running in a foot race to see which cow is the fastest.

Viewed from above, each cow is represented by a unit-length horizontal line segment, specified by the coordinates of its left corner point at time t=0.  For example, (-3,6) would specify a cow who at time t=0 is represented by the segment from (-3,6) to (-2,6).  Each cow is moving to the right (in the +x direction) at a certain rate, specified by the integer amount of time it takes her to move 1 unit to the right.

FJ is not particularly thrilled that his cows are outside running instead of in the barn producing milk.  He plans to admonish them with a stern lecture after the race ends.  In order to determine which of his cows are participating in the race, FJ situates himself at (0,0) and looks along a ray extending in the +y direction.  As the race unfolds, FJ sees a cow if she is ever the first cow visible along this ray.  That is, a cow might not be visible if another cow is "in front" of her during the entire time she crosses FJ's line of sight.

Please compute the number of cows FJ can see during the entire race.

inputFormat:
INPUT: (file stampede.in)

The first line of the input contains N.  Each of the following N lines describes a cow with three integers x y r, corresponding to a cow whose left endpoint is at (x,y) at time t=0, moving to the right at a continuous speed of 1 unit of distance every r units of time.  The value of x is in the range -1000..-1, the value of y is in the range 1..1,000,000 (and distinct for every cow, to prevent any possible collisions), and the value of r is in the range 1..1,000,000.

outputFormat:
OUTPUT: (file stampede.out)

A single integer, specifying the number of cows FJ can see during the

entire race (from t=0 onward).

translation: FJ 站在原点上向 $y$ 轴正半轴看，然后有一群奶牛从他眼前飞过。初始时，这些奶牛初始都在第二象限，第 $i$ 只奶牛尾巴在 $(X_i,Y_i)$，头在 $(X_i+1,Y_i)$，并且以平均 $C_i$ 秒一个单位的速度匀速向右移动着。 FJ 能看见一匹奶牛当且仅当它身体任意某部位 $x$ 坐标为 $0$ 时，没有其它 $y$ 坐标小于此奶牛的奶牛身体某部位 $x$ 坐标为 $0$。问 FJ 能看见多少奶牛？

hint:
SOLUTION NOTES:

FJ can see cows 1 and 2 but not cow 3.


title: [USACO15JAN] Cow Routing S

description:
Tired of the cold winter weather on her farm, Bessie the cow plans to fly to a warmer destination for vacation.  Unfortunately, she

discovers that only one airline, Air Bovinia, is willing to sell tickets to cows, and that these tickets are somewhat complicated in structure.

Air Bovinia owns N planes (1 <= N <= 1000), each of which flies on a specific "route" consisting of two or more cities.  For example, one plane might fly on a route that starts at city 1, then flies to city 5, then flies to city 2, and then finally flies to city 8.  No city appears multiple times in a route.  If Bessie chooses to utilize a route, she can board at any city along the route and then disembark at any city later along the route.  She does not need to board at the first city or disembark at the last city.  Each route has a certain cost, which Bessie must pay if she uses any part of the route, irrespective of the number of cities she visits along the route.  If Bessie uses a route multiple times during her travel (that is, if she leaves the route and later comes back to use it from antoher city), she must pay for it each time it is used.

Bessie would like to find the cheapest way to travel from her farm (in city A) to her tropical destination (city B). Please help her decide what is the minimum cost she must pay, and also the smallest number of individual flights she must use take to achieve this minimum cost.

inputFormat:
INPUT: (file cowroute.in)

The first line of input contains A, B, and N, separated by spaces.

The next 2N lines describe the available routes, in two lines per route. The first line contains the cost of using the route (an integer in the range 1..1,000,000,000), and the number of cities along the route (an integer in the range 1..100).  The second line contains a list of the cities in order along the route.  Each city is identified by an integer in the range 1..1000.  Note that the cost of an

itinerary can easily add up to more than can fit into a 32-bit integer, so you should probably use 64-bit integers (e.g., "long long" integers in C/C++).

outputFormat:
OUTPUT: (file cowroute.out)

Output the minimum cost of an itinerary that Bessie can use to travel

from city A to city B, as well as the minimum number of individual

flights required to achieve this minimum cost.  If there is no

solution, output "-1 -1" (quotes for clarity) on a single line.

translation:
### 题目描述

Bessie 对她农场那寒冷的天气感到厌烦，于是她准备坐飞机到一个更温暖的地方度假。不幸的是，她发现只有一个航空公司：Air Bovinia，愿意卖票给牛，并且这些票的结构有些复杂。

Air Bovinia 拥有 $n$ 架飞机，每架飞机都有一个经过两个及以上的城市的特殊航线。举个例子：一架飞机可以从城市 $1$ 出发，然后飞往城市 $5$，再飞到城市 $2$，最后飞到城市 $8$。注意**航线是单向的**。任何城市都不会在同一条航线上出现多次。如果 Bessie 选择了一条航线，那么她可以从航线上的任意一个城市上飞机，然后在途中任意一个城市下飞机。他不必从航线的起点上飞机，再从航线的终点下飞机。每条航线都有一个确定的花费，只要它搭乘了这个航班，她就必须支付这个航班的全额花费，不论她途经了几个城市。如果 Bessie 多次搭乘了某个航班，那么每次搭乘 Bessie 都必须支付航班的花费。

Bessie 想要找到从她农场所在的城市（城市 $A$）到她目的地所在城市（城市 $B$）最便宜的路线。请你告诉她他最少要花多少钱，并告诉她在此基础上她最少要**经过几段航线**，也即经过的城市数量 $-1$（包括起点和终点）。

### 输入格式

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

接下来 $2n$ 行，每两行描述一次航班。第一行包括航线的花费 $cost$ 与经过的城市数 $len$。第二行 $len$ 个整数，表示航班依次经过的城市。

### 输出格式

一行两个整数，输出 Bessie 旅行最少要花的钱以及在此基础上最少的经过航线数量。

如果 Bessie 不能从她的农场到达她的目的地，则输出 `-1 -1`。

### 数据范围

$1\le n\le 1000$，$1\le cost\le 10^9$，$1\le len\le 100$。城市的编号均不超过 $1000$。

可能需要开 `long long`。


title: [USACO15JAN] Meeting Time S

description:
Bessie and her sister Elsie want to travel from the barn to their favorite field, such that they leave at exactly the same time from the barn, and also arrive at exactly the same time at their favorite field.

The farm is a collection of N fields (1 <= N <= 100) numbered 1..N, where field 1 contains the barn and field N is the favorite field. The farm is built on the side of a hill, with field X being higher in elevation than field Y if X < Y.  An assortment of M paths connect pairs of fields.  However, since each path is rather steep, it can only be followed in a downhill direction. For example, a path

connecting field 5 with field 8 could be followed in the 5 -> 8 direction but not the other way, since this would be uphill.  Each pair of fields is connected by at most one path, so M <= N(N-1)/2.

It might take Bessie and Elsie different amounts of time to follow a path; for example, Bessie might take 10 units of time, and Elsie 20. Moreover, Bessie and Elsie only consume time when traveling on paths between fields -- since they are in a hurry, they always travel through a field in essentially zero time, never waiting around anywhere.

Please help determine the shortest amount of time Bessie and Elsie must take in order to reach their favorite field at exactly the same moment.

inputFormat:
INPUT: (file meeting.in)

The first input line contains N and M, separated by a space.

Each of the following M lines describes a path using four integers A B C D, where A and B (with A < B) are the fields connected by the path, C is the time required for Bessie to follow the path, and D is the time required for Elsie to follow the path.  Both C and D are in the range 1..100.

outputFormat:
OUTPUT (file meeting.out)

A single integer, giving the minimum time required for Bessie and

Elsie to travel to their favorite field and arrive at the same moment.

If this is impossible, or if there is no way for Bessie or Elsie to reach

the favorite field at all, output the word IMPOSSIBLE on a single line.

translation:
#### 题目描述：

$\texttt{Bessie}$ 和她的妹妹 $\texttt{Elsie}$ 想从粮仓去她们最喜欢的田地，也就是能够使她们一起从粮仓离开，并且能同一时间到达的田地。

这个农场是由 $N$ 块 $(1\leq N\leq 100)$ 编号为 $1\cdots N$ 的田地构成的，第一块田地就是粮仓，并且第 $N$ 块田地是她们最喜欢的田地。

这个农场建在山的一边，所以，如果 $X < Y$ 的话则满足第 $X$ 块田地的高度要高于第 $Y$ 块田地的高度。在这之中，有 $M$ 条交错纵横的路径将不同的田地连接起来。

不过，显而易见的是，因为每条路都太陡了，所以这些小路只能沿着从高到低的方向走。例如，一条连接第 $5$ 块田地和 $8$ 块田地的小路只能沿着 $5\to 8$ 的方向走，而不能沿着其他方向，因为那样会成为上坡路。每两块田地最多只能有一条路径相连接，所以一定有 $M \leq \dfrac{N(N-1)}{2}$。

有可能的是，$\texttt{Bessie}$ 和 $\texttt{Elsie}$ 两个人走同一条小路会耗费不同的时间；比如，通过同一条小路，$\texttt{Bessie}$ 可能会耗费 $10$ 个单位的时间，而 $\texttt{Elsie}$ 会耗费 $20$ 个单位的时间。

此外，$\texttt{Bessie}$ 和 $\texttt{Elsie}$ 只会在通过连接两块田地的小路时耗费时间——因为她们太匆忙了，在穿过田地时不会耗费任何时间，也从来不在任何地方停下来等待。

现在，请你判断出，能够满足使 $\texttt{Bessie}$ 和 $\texttt{Elsie}$ 同时出发并且同时到达她们喜欢的田地的最短的时间。

#### 输入格式：

第一行输入 $N$ 和 $M$，中间用空格分开。

接下来的 $M$ 行，每行有四个整数 $A,B,C,D$，其中，$A$ 和$B(A<B)$ 代表着两块用这条小路连接的田地，$C$ 代表 $\texttt{Bessie}$ 通过这条小路的时间，而 $D$ 代表 $\texttt{Elsie}$ 通过这条小路的时间。$C$ 和 $D$ 均在 $1\cdots100$ 的范围之内。

#### 输出格式：

一个整数，输出的是能够使两人同时出发并且同时到达目的地的最短时间，如果没有满足条件的答案，则输出 `IMPOSSIBLE`。

#### 说明与提示：

$\texttt{Bessie}$ 在每一条路都比 $\texttt{Elsie}$ 快两倍。

如果 $\texttt{Bessie}$ 经过 $1\to 2\to 3$ 的路线，$\texttt{Elsie}$ 经过 $1\to 3$ 的路线，他们可以同时到达。

hint:
SOLUTION NOTES:

Bessie is twice as fast as Elsie on each path, but if Bessie takes the

path 1->2->3 and Elsie takes the path 1->3 they will arrive at the

same time.


title: [USACO15JAN] Cow Rectangles G

description: The locations of Farmer John's N cows (1 <= N <= 500) are described by distinct points in the 2D plane.  The cows belong to two different breeds: Holsteins and Guernseys.  Farmer John wants to build a rectangular fence with sides parallel to the coordinate axes enclosing only Holsteins, with no Guernseys (a cow counts as enclosed even if it is on the boundary of the fence).  Among all such fences, Farmer John wants to build a fence enclosing the maximum number of Holsteins.  And among all these fences, Farmer John wants to build a fence of minimum possible area.  Please determine this area.  A fence of zero width or height is allowable.

inputFormat:
INPUT: (file cowrect.in)

The first line of input contains N.  Each of the next N lines

describes a cow, and contains two integers and a character. The integers indicate a point (x,y) (0 <= x, y <= 1000) at which the cow is located. The character is H or G, indicating the cow's breed.  No two cows are located at the same point, and there is always at least one Holstein.

outputFormat:
OUTPUT: (file cowrect.out)

Print two integers. The first line should contain the maximum number

of Holsteins that can be enclosed by a fence containing no Guernseys,

and second line should contain the minimum area enclosed by such a

fence.

translation:
约翰的 $N(1 \le N \le 500)$ 头奶牛的位置由坐标平面上的点来描述。这些奶牛分为两种：Holsteins 和 Guernseys。约翰想要修建一个矩形的围栏，围栏的边平行于 $x$ 轴或者 $y$ 轴，并且要求围栏中只有 Holsteins 类型的奶牛（一头奶牛在围栏的边边上也算在围栏以内）。

约翰想要使围栏围住进可能多的 Holsteins 奶牛，在此基础上，约翰希望围栏构成的矩形的面积尽可能小，请你计算出这个最小面积。

注意：围栏的长或宽为 $0$ 的情况是允许的。


title: [USACO15JAN] Moovie Mooving G

description:
Bessie is out at the movies.  Being mischievous as always, she has decided to hide from Farmer John for L (1 <= L <= 100,000,000) minutes, during which time she wants to watch movies continuously. She has N (1 <= N <= 20) movies to choose from, each of which has a certain duration and a set of showtimes during the day.  Bessie may enter and exit a movie at any time during one if its showtimes, but she does not want to ever visit the same movie twice, and she cannot switch to another showtime of the same movie that overlaps the current showtime.

Help Bessie by determining if it is possible for her to achieve her goal of watching movies continuously from time 0 through time L.  If it is, determine the minimum number of movies she needs to see to achieve this goal (Bessie gets confused with plot lines if she watches too many movies).

奶牛贝西想连续看 $L$（$1 \le L \le 10^8$）分钟的电影，有 $N$（$1 \le N \le 20$）部电影可供选择，每部电影会在一天的不同时段放映。

贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影，所以每部电影她最多看到一次。她也不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。

请帮贝西计算她能够做到从 $0$ 到 $L$ 分钟连续不断地观看电影，如果能，请计算她最少看几部电影就行了。

inputFormat:
INPUT: (file movie.in)

The first line of input contains N and L.

The next N lines each describe a movie.  They begin with its integer duration, D (1 <= D <= L) and the number of showtimes, C (1 <= C <= 1000).  The remaining C integers on the same line are each in the range 0..L, and give the starting time of one of the showings of the movie.  Showtimes are distinct, in the range 0..L, and given in increasing order.

outputFormat:
UTPUT: (file movie.out)

A single integer indicating the minimum number of movies that Bessie

needs to see to achieve her goal.  If this is impossible output -1

instead.

hint:
SOLUTION NOTES:

Bessie should attend the first showing of the fourth movie from time 0

to time 20.  Then she watches the first showing of the first movie

from time 20 to time 65.  Finally she watches the last showing of the

second movie from time 65 to time 100.


title: [USACO15JAN] Grass Cownoisseur G

description:
In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm.  The farm consists of N fields, conveniently numbered 1..N, with each one-way cow path connecting a pair of fields.  For example, if a path connects from field X to field Y, then cows are allowed to travel from X to Y but not from Y to X.

Bessie the cow, as we all know, enjoys eating grass from as many fields as possible.  She always starts in field 1 at the beginning of the day and visits a sequence of fields, returning to field 1 at the end of the day.  She tries to maximize the number of distinct fields along her route, since she gets to eat the grass in each one (if she visits a field multiple times, she only eats the grass there once).

As one might imagine, Bessie is not particularly happy about the one-way restriction on FJ's paths, since this will likely reduce the number of distinct fields she can possibly visit along her daily route.  She wonders how much grass she will be able to eat if she breaks the rules and follows up to one path in the wrong direction. Please compute the maximum number of distinct fields she can visit along a route starting and ending at field 1, where she can follow up to one path along the route in the wrong direction.  Bessie can only travel backwards at most once in her journey.  In particular, she cannot even take the same path backwards twice.

约翰有 $n$ 块草场，编号 $1$ 到 $n$，这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家，她想到达尽可能多的草场去品尝牧草。

贝西总是从 $1$ 号草场出发，最后回到 $1$ 号草场。她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次。因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行。问，贝西最多能吃到多少个草场的牧草。

inputFormat:
INPUT: (file grass.in)

The first line of input contains N and M, giving the number of fields and the number of one-way paths (1 <= N, M <= 100,000).

The following M lines each describe a one-way cow path.  Each line contains two distinct field numbers X and Y, corresponding to a cow path from X to Y.  The same cow path will never appear more than once.

输入：

第一行：草场数 $n$，道路数 $m$。

以下 $m$ 行，每行 $x$ 和 $y$ 表明有 $x$ 到 $y$ 的单向边，不会有重复的道路出现。

outputFormat:
OUTPUT: (file grass.out)

A single line indicating the maximum number of distinct fields Bessie

can visit along a route starting and ending at field 1, given that she can

follow at most one path along this route in the wrong direction.

输出：

一个数，逆行一次最多可以走几个草场。

hint:
SOLUTION NOTES:

Here is an ASCII drawing of the sample input:

```cpp
v---3-->6
7   | \ |
^\  v  \|
| \ 1   |
|   |   v
|   v   5
4<--2---^
```

Bessie can visit pastures 1, 2, 4, 7, 2, 5, 3, 1 by traveling

backwards on the path between 5 and 3.  When she arrives at 3 she

cannot reach 6 without following another backwards path.


title: [USACO15FEB] Cow Hopscotch G

description:
Just like humans enjoy playing the game of Hopscotch, Farmer John's cows have invented a variant of the game for themselves to play.  Being played by clumsy animals weighing nearly a ton, Cow Hopscotch almost always ends in disaster, but this has surprisingly not deterred the cows from attempting to play nearly every afternoon.

The game is played on an R by C grid (2 <= R <= 750, 2 <= C <= 750), where each square is labeled with an integer in the range 1..K (1 <= K <= R\*C).  Cows start in the top-left square and move to the bottom-right square by a sequence of jumps, where a jump is valid if and only if

1) You are jumping to a square labeled with a different integer than your current square,

2) The square that you are jumping to is at least one row below the current square that you are on, and

3) The square that you are jumping to is at least one column to the right of the current square that you are on.

Please help the cows compute the number of different possible sequences of valid jumps that will take them from the top-left square to the bottom-right square.

就像人类喜欢跳格子游戏一样，FJ的奶牛们发明了一种新的跳格子游戏。虽然这种接近一吨的笨拙的动物玩跳格子游戏几乎总是不愉快地结束，但是这并没有阻止奶牛们在每天下午参加跳格子游戏

游戏在一个R\*C的网格上进行，每个格子有一个取值在1-k之间的整数标号，奶牛开始在左上角的格子，目的是通过若干次跳跃后到达右下角的格子，当且仅当格子A和格子B满足如下条件时能从格子A跳到格子B：

1.B格子在A格子的严格右方(B的列号严格大于A的列号)

2.B格子在A格子的严格下方(B的行号严格大于A的行号)

3.B格子的标号和A格子的标号不同

请你帮助奶牛计算出从左上角的格子到右下角的格子一共有多少种不同的方案

inputFormat:
The first line contains the integers R, C, and K.

The next R lines will each contain C integers, each in the range 1..K.

outputFormat: Output the number of different ways one can jump from the top-left square to the bottom-right square, mod 1000000007.


title: [USACO15FEB] Censoring G

description:
FJ 把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过 $10^5$ 的字符串 $s$。他有一个包含 $n$ 个单词的列表，列表里的 $n$ 个单词记为 $t_1 \cdots t_n$。他希望从 $s$ 中删除这些单词。

FJ 每次在 $s$ 中找到最早出现的列表中的单词（最早出现指该单词的开始位置最小），然后从 $s$ 中删除这个单词。他重复这个操作直到 $s$ 中没有列表里的单词为止。注意删除一个单词后可能会导致 $s$ 中出现另一个列表中的单词。

FJ 注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在 $s$ 中出现的开始位置是互不相同的。

请帮助 FJ 完成这些操作并输出最后的 $s$。

inputFormat:
第一行是一个字符串，表示文章 $s$。

第二行有一个整数，表示单词列表的单词个数 $n$。

第 $3$ 到第 $(n + 2)$ 行，每行一个字符串，第 $(i + 2)$ 行的字符串 $t_i$ 表示第 $i$ 个单词。

outputFormat: 输出一行一个字符串，表示操作结束后的 $s$。

samples:
begintheescapexecutionatthebreakofdawn
2
escape
execution

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

对于全部的测试点，保证：

- $1 \leq |s|, \sum\limits_{i = 1}^n |t_i|, n \leq 10^5$。
- 字符串均只含小写字母。
- 操作结束后 $s$ 不会被删成空串。
- 对于所有的 $i \neq j$，$t_i$ 不是 $t_j$ 的子串。

其中对于一个字符串 $x$，约定 $|x|$ 表示 $x$ 的长度。

---

#### 提示

操作过程中 $s$ 有可能某一个前缀子串被完全删除，请格外注意这一点。


title: [USACO15FEB] Fencing the Herd G

description:
Farmer John 需要你帮助他决定在哪里建造形状是一条无限长的直线的栅栏来限制他的牛的活动。他选出了几个可能的建造栅栏的位置，你需要帮助他判断哪些栅栏是有用的。一个栅栏是有用的当且仅当所有奶牛都在栅栏的同一侧。（如果有牛群在栅栏所在的直线上，那么栅栏是没用的），Farmer John 将会多次询问你一个栅栏是否有用，如果这个栅栏是有用的，需要输出 `YES`，反之输出 `NO`。

另外，Farmer John 也可能会带来一些新的奶牛加入这个牛群。一头牛加入之后，以后的所有询问中，这头牛也需要与其它的牛在栅栏的同一侧。

inputFormat:
第一行，两个正整数 $n,q$，表示初始时牛群的数量与询问个数；

后 $n$ 行，每行两个整数 $x,y$，表示一个牛群的初始位置；

后 $q$ 行，每行多个整数，表示一次询问，询问的格式如下：

- 1 $x$ $y$：表示一个新的牛群加入了牧场，驻留在 $(x,y)$ 上；
- 2 $A$ $B$ $C$：表示 Farmer John 询问栅栏 $Ax+By=C$ 是否有用。

outputFormat: 对于每个 $2$ 类型的询问，如果栅栏有用，输出 `YES`，否则输出 `NO`。

hint:
直线 $2x+2y=3$ 使得初始的三个牛群都在同侧；然而在该栅栏另一侧的牛群 $(1,1)$ 的加入使得它没有用了。

直线 $y=1$ 没用因为牛群 $(0,1)$，$(1,1)$ 恰好在它上面。

---

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^5$，$1\leq q\leq 10^5$，所有牛群的坐标都各不相同且满足 $-10^9\leq x,y\leq 10^9$，$-10^9\leq A,B\leq 10^9$，$-10^{18}\leq C\leq 10^{18}$。

数据保证不存在栅栏满足 $A=B=0$。


title: [USACO15OPEN] Bessie Goes Moo S

description:
Farmer John and Bessie the cow love to exchange math puzzles in their free time.

The last puzzle FJ gave Bessie was quite difficult and she failed to solve it.

Now she wants to get even with FJ by giving him a challenging puzzle.

Bessie gives FJ the expression $(B+E+S+S+I+E)(G+O+E+S)(M+O+O)$, containing the seven variables $B,E,S,I,G,O,M$ (the "$O$" is a variable, not a zero).  For each variable, she gives FJ a list of up to 500 integer values the variable can possibly take.

She asks FJ to count the number of different ways he can assign values to the variables so the entire expression evaluates to a multiple of 7.

Note that the answer to this problem can be too large to fit into a 32-bit integer, so you probably want to use 64-bit integers (e.g., "long long"s in C or C++).

给定七个变量 $B,E,S,I,G,O,M$ 中每个变量的所有可能值。求使得 $(B+E+S+S+I+E)(G+O+E+S)(M+O+O)$ 被 $7$ 整除的方案有多少种。

inputFormat:
The first line of the input contains an integer $N$.  The next $N$ lines each contain a variable and a possible value for that variable.

Each variable will appear in this list at least once and at most 500 times. No possible value will be listed more than once for the same variable. All possible values will be in the range $-10^5$ to $10^5$.

outputFormat: Print a single integer, giving the number of ways FJ can assign values to variables so the expression above evaluates to a multiple of 7.


title: [USACO15OPEN] Trapped in the Haybales S

description:
Farmer John has received a shipment of $N$ large hay bales

($1 \le N \le 100,000$), and placed them at various locations along the road

connecting the barn with his house.  Each bale $j$ has a size $S_j$ and a

distinct position $P_j$ giving its location along the one-dimensional road.

Bessie the cow is currently located at position $B$, where there is no hay bale.

Bessie the cow can move around freely along the road, even up to the position at

which a bale is located, but she cannot cross through this position.  As an

exception, if she runs in the same direction for $D$ units of distance, she

builds up enough speed to break through and permanently eliminate any hay bale

of size strictly less than $D$.  Of course, after doing this, she might

open up more space to allow her to make a run at other hay bales, eliminating

them as well.

FJ is currently re-painting his house and his barn, and wants to make sure

Bessie cannot reach either one (cows and fresh paint do not make a good

combination!)  Accordingly, FJ wants to make sure Bessie never breaks through

the leftmost or rightmost hay bale, so she stays effectively trapped within the

hay bales.  FJ has the ability to add hay to a single bale of his choosing to

help keep Bessie trapped.  Please help him determine the minimum amount of extra

size he needs to add to some bale to ensure Bessie stays trapped.

inputFormat:
The first line of input contains $N$ as well as Bessie's initial position $B$.

Each of the next $N$ lines describes a bale, and contains two integers giving

its size and position.  All sizes and positions are in the range $1\ldots 10^9$.

outputFormat:
Print a single integer, giving the minimum amount of hay FJ needs to add to

prevent Bessie from escaping.  Print -1 if it is impossible to prevent Bessie's

escape.

translation:
FJ 收到了 $N$ 捆干草，并将它们放置在连接房屋与谷仓的道路上。第 $j$ 捆干草的大小为 $S_j$，位置为 $P_j$。Bessie 一开始在 $B$ 处，不与任何一捆干草的位置重合。

Bessie 可以在干草捆之间任意移动（也可以到达干草捆所在的位置），但不能越过干草捆。但凡事总有例外：当 Bessie 进行了长度为 $D$ 的冲刺后，她就可以击碎一捆大小严格小于 $D$ 的干草，这意味着这捆干草不复存在。

由于某些原因，FJ 希望把 Bessie 困在最左边与最右边的干草捆之间。为此，他希望将某一捆干草的大小增加一些。如果可能把 Bessie 困住，请输出他最少需要增加多少干草；否则输出 `-1`。

$1 \leqslant N \leqslant 10^5$，$1 \leqslant S_i, P_i, B \leqslant 10^9$。

#### 输入格式

第一行，两个整数 $N, B$，分别表示干草捆数量与 Bessie 所在位置。

接下来 $N$ 行，第 $i$ 行为两个整数 $S_i, P_i$，分别表示第 $i$ 捆干草的大小与位置。

#### 输出格式

如果可能把 Bessie 困住，输出一行一个整数，表示最少需要增加多少干草；否则输出 `-1`。

Translated by [KHIN](/user/236807).


title: [USACO15OPEN] Bessie's Birthday Buffet S

description:
For Bessie the cow’s birthday, Farmer John has given her free reign over one

of his best fields to eat grass.

The field is covered in $N$ patches of grass ($1 \le N \le 1000$), conveniently

numbered $1\ldots N$, that each have a distinct quality value.  If Bessie eats

grass of quality $Q$, she gains $Q$ units of energy.  Each patch is connected to

up to 10 neighboring patches via bi-directional paths, and it takes Bessie $E$

units of energy to move between adjacent patches ($1 \le E \le 1,000,000$).

Bessie can choose to start grazing in any patch she wishes, and she wants to

stop grazing once she has accumulated a maximum amount of energy.

Unfortunately, Bessie is a picky bovine, and once she eats grass of a certain

quality, she’ll never eat grass at or below that quality level again!  She is

still happy to walk through patches without eating their grass; in fact, she

might find it beneficial to walk through a patch of high-quality grass without

eating it, only to return later for a tasty snack.

Please help determine the maximum amount of energy Bessie can accumulate.

为了庆祝奶牛Bessie的生日，Farmer John给了她一块最好的牧场，让她自由的享用。

牧场上一共有N块草地（1≤N≤1000），编号为1...N，每块草地上牧草的质量都不同。

如果Bessie吃掉的草地上牧草质量为Q，她可以获得Q单位的能量。

每块草地最多和10块草地有相连的道路，在相连的两个草地之间走动需要消耗E单位的能量(1≤E≤1,000,000)。

Bessie可以从任意一块草地开始吃草，并且想要在获得了最多能量的时候停止。

有点遗憾的，Bessie是一头挑食的奶牛，一旦她吃过了一定质量的牧草，她就不会再吃相同或更低质量的牧草！但是她仍然很愿意路过某些草地，而不吃它们。实际上，她发现路过一块高质量的草地而不吃它，等一下返回再去享用，有时会更有利！

请帮忙计算Bessie能够获得的能量的最大值。

inputFormat:
The first line of input contains $N$ and $E$.  Each of the remaining $N$ lines

describe a patch of grass.  They contain two integers $Q$ and $D$ giving the

quality of the patch (in the range $1\ldots 1,000,000$) and its number of

neighbors.  The remaining $D$ numbers on the line specify the neighbors.

1行：包含两个整数N和E。

接下来N行：每行描述一块草地，首先两个整数Q和D，分别表示草地上牧草的质量（范围1…1,000,000）和相连的草地数量。然后D个整数表示相连的草地。

outputFormat:
Please output the maximum amount of energy Bessie can accumulate.

输出Bessie能够获得的能量的最大值。

hint:
Bessie starts at patch 4 gaining 5 units of energy from the grass there.  She

then takes the path to patch 5 losing 2 units of energy during her travel.

She refuses to eat the lower quality grass at patch 5 and travels to patch 3

again losing 2 units of energy.  Finally she eats the grass at patch 3 gaining 6 units of energy

for a total of 7 energy.

Note tha the sample case above is different from test case 1 when you submit.

感谢@蒟蒻orz神犇 提供翻译


title: [USACO15OPEN] Palindromic Paths G

description:
Farmer John's farm is in the shape of an $N \times N$ grid of fields ($1 \le N \le 500$), each labeled with a letter in the alphabet.  For example:

```cpp
ABCD
BXZX
CDXB
WCBA
```
Each day, Bessie the cow walks from the upper-left field to the lower-right field, each step taking her either one field to the right or one field downward. Bessie keeps track of the string that she generates during this process, built from the letters she walks across.  She gets very disoriented, however, if this string is a palindrome (reading the same forward as backward), since she gets confused about which direction she had walked.   Please help Bessie determine the number of distinct routes she can take that  correspond to palindromes.  Different ways of obtaining the same palindrome count multiple times.  Please print your answer modulo 1,000,000,007.

农夫 FJ 的农场是一个 $N\times N$ 的正方形矩阵（$2\le N\le 500$），每一块用一个字母作标记。比如说：

```cpp
ABCD
BXZX
CDXB
WCBA
```

某一天，FJ 从农场的左上角走到右下角，当然啦，每次他只能往右或者往下走一格。FJ 把他走过的路径记录下来。现在，请你把他统计一下，所有路径中，回文串的数量（从前往后读和从后往前读一模一样的字符串称为回文串）。

inputFormat:
The first line of input contains $N$, and the remaining $N$ lines contain the

$N$ rows of the grid of fields.  Each row contains $N$ characters that are

in the range A..Z.

第一行包括一个整数 $N$，表示农场的大小，接下来输入一个 $N\times N$ 的字母矩阵。

outputFormat:
Please output the number of distinct palindromic routes Bessie can take,

modulo 1,000,000,007.

输出一个整数，表示回文串的数量。

hint:
Bessie can make the following palindromes

1 x "ABCDCBA"

1 x "ABCWCBA"

6 x "ABXZXBA"

4 x "ABXDXBA"


title: [USACO15OPEN] Trapped in the Haybales G

description:
Farmer John has received a shipment of N large hay bales ($1 \le N \le 100,000$), and placed them at various locations along the road leading to his barn. Unfortunately, he completely forgets that Bessie the cow is out grazing along the road, and she may now be trapped within the bales! Each bale $j$ has a size $S_j$ and a position $P_j$ giving its location along the one-dimensional road.  Bessie the cow can move around freely along the road, even up to the position at which a bale is located, but she cannot cross through this position.  As an exception, if she runs in the same direction for $D$ units of distance, she builds up enough speed to break through and permanently eliminate any hay bale of size strictly less than $D$.  Of course, after doing this, she might open up more space to allow her to make a run at other hay bales, eliminating them as well.

Bessie can escape to freedom if she can eventually break through either the  leftmost or rightmost hay bale.  Please compute the total area of the road consisting of real-valued starting positions from which Bessie cannot escape.

inputFormat:
The first line of input contains $N$.  Each of the next $N$ lines describes a

bale, and contains two integers giving its size and position, each in the range

$1\ldots 10^9$. All positions are distinct.

outputFormat:
Print a single integer, giving the area of the road from which Bessie cannot

escape.

translation:
### 题目描述
农夫约翰最近买了N个干草堆，他把这些干草堆都放在家和农场之间的一条直路上，每个干草堆的位置各不相同。不幸的是，他忘记了他的奶牛贝里斯正外出吃草，贝里斯也许会被这些干草堆所限制住！干草堆j的大小是Sj，在Pj的位置上。贝里斯从一个不是干草堆的地方出发，他可以自由的在这条直线上移动，他不能越过干草堆。有一种特殊的情况， 他可以往一个方向连续跑了D的距离以后，他就可以积累足够的能量，然后就可以消除小于D的干草堆。当然了，在消除了一个干草堆以后，他就可以有更多的空间来跑步和积蓄能量了。当贝里斯成功消除了第一个或者最后一个干草堆的时候，他就可以获得自由了，请你计算使得贝里斯不能获得自由的初始位置的区间总和。
### 输入
第一行是一个正整数N，表示干草堆的数量。接下来N行，每行两个正整数，分别表示干草堆的大小和位置。
### 输出
输出使得贝里斯不能获得自由的初始位置的区间总和。

感谢@sxyugao 提供的翻译


title: [USACO15DEC] Max Flow P

description:
Farmer John has installed a new system of $N-1$ pipes to transport milk between the $N$ stalls in his barn ($2 \leq N \leq 50,000$), conveniently numbered $1 \ldots N$.  Each pipe connects a pair of stalls,  and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between $K$ pairs of stalls ($1 \leq K \leq 100,000$).  For the $i$th such pair,  you are told two stalls $s_i$ and $t_i$, endpoints of a path along which milk is being pumped at a unit rate.  FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the $K$ paths along which milk is being pumped.  Please help him determine the maximum amount of milk being pumped through any stall.  If milk is being pumped along a path from $s_i$ to $t_i$, then it counts as being pumped through the endpoint stalls $s_i$ and

$t_i$, as well as through every stall along the path between them.

FJ 给他的牛棚的 $N$ 个隔间之间安装了 $N-1$ 根管道，隔间编号从 $1$ 到 $N$。所有隔间都被管道连通了。

FJ 有 $K$ 条运输牛奶的路线，第 $i$ 条路线从隔间 $s_i$ 运输到隔间 $t_i$。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

inputFormat:
The first line of the input contains $N$ and $K$.

The next $N-1$ lines each contain two integers $x$ and $y$ ($x \ne y$) describing a pipe

between stalls $x$ and $y$.

The next $K$ lines each contain two integers $s$ and $t$ describing the endpoint

stalls of a path through  which milk is being pumped.

第一行输入两个整数 $N$ 和 $K$。

接下来 $N-1$ 行每行输入两个整数 $x$ 和 $y$，其中 $x \ne y$。表示一根在牛棚 $x$ 和 $y$ 之间的管道。

接下来 $K$ 行每行两个整数 $s$ 和 $t$，描述一条从 $s$ 到 $t$ 的运输牛奶的路线。

outputFormat:
An integer specifying the maximum amount of milk pumped through any stall in the barn.

一个整数，表示压力最大的隔间的压力是多少。


title: [USACO15DEC] High Card Low Card P

description:
Bessie the cow is a hu e fan of card games, which is quite surprising, given her lack of opposable thumbs.  Unfortunately, none of the other cows in the herd are good opponents.  They are so bad, in fact, that they always play in a completely predictable fashion!  Nonetheless, it can still be a challenge for Bessie to figure out how to win.

Bessie and her friend Elsie are currently playing a simple card game where they take a deck of $2N$ cards, conveniently numbered $1 \ldots 2N$, and divide them into $N$ cards for Bessie and $N$ cards for Elsie.   The two then play $N$ rounds, where in each round Bessie and Elsie both play a single card.  Initially, the player who plays the highest card earns a point.  However, at one point  during the game, Bessie can decide to switch the rules so that for the rest of the game, the player who plays the lowest card wins a point.  Bessie can choose not to use this option, leaving the entire game in "high card wins" mode, or she can even invoke the option right away, making the entire game follow the "low card wins" rule.

Given that Bessie can predict the order in which Elsie will play her cards, please determine the maximum number of points Bessie can win.

贝西很喜欢玩一种纸牌游戏。

贝西和她的朋友艾尔西正在玩这个简单的纸牌游戏。游戏有 $2N$ 张牌，牌上的数字是 $1$ 到 $2N$。把这些牌分成两份，贝西有 $N$ 张，艾尔西有另外 $N$ 张。接下来她们进行 $N$ 轮出牌，每次各出一张牌。一开始，谁出的牌上的数字大，谁就获得这一轮的胜利。贝西有一个特殊权利，她可以在任意一个时刻把原本数字大的获胜的规则改成数字小的获胜，这个改变将会一直持续到游戏结束。特别的，贝西可以从第一轮开始就使用小牌获胜的规则，也可以直到最后一轮都还杂使用大牌获胜的规则。

现在，贝西已经知道了艾尔西出牌的顺序，她想知道她最多能够赢多少轮。

inputFormat:
The first line of input contains the value of N ($2 \leq N \leq 50,000$).

The next N lines contain the cards that Elsie will play in each of the

successive rounds of the game.  Note that it is easy to determine Bessie's cards

from this information.

outputFormat: Output a single line giving the maximum number of points Bessie can score.

hint:
Here, Bessie must have cards 2, 5, and 6, and 7 in her hand, and she can use

these to win at most 3 points.  For example, she can defeat the 1 card and then

switch the rules to "low card wins", after which she can win two more rounds.


title: [USACO15DEC] Counting Haybale P

description:
Farmer John is trying to hire contractors to help rearrange his farm, but so far all of them have quit when they saw the complicated sequence of instructions FJ wanted them to follow.  Left to complete the project by himself, he realizes that indeed, he has made the project perhaps more  complicated than necessary.  Please help him follow his instructions to  complete the farm upgrade.

FJ's farm consists of $N$ fields in a row, conveniently numbered $1 \ldots N$. In each field there can be any number of haybales.  Farmer John's instructions contain three types of entries:

1) Given a contiguous interval of fields, add a new haybale to each field.

2) Given a contiguous interval of fields, determine the minimum number of haybales in a field within that interval.

3) Given a contiguous interval of fields, count the total number of haybales  inside that interval.

inputFormat:
The first line contains two positive integers, $N$ ($1 \leq N \leq 200,000$) and

$Q$ ($1 \leq Q \leq 100,000$).

The next line contains $N$ nonnegative integers, each at most 100,000,

indicating how many haybales are initially in each field.

Each of the next $Q$ lines contains a single uppercase letter, either M, P or S,

followed by either two positive integers $A$ and $B$ ($1 \leq A \leq B \leq N$),

or three positive integers $A$, $B$, and $C$ ($1 \leq A \leq B \leq N$;

$1 \leq C \leq 100,000$).  There will be three positive integers if and only if

the uppercase letter is P.

If the letter is M, print the minimum number of haybales in the interval of fields

from $A \ldots B$.

If the letter is P, put $C$ new haybales in each field in the interval of fields

from $A \ldots B$.

If the letter is S, print the total number of haybales found within interval of

fields from $A \ldots B$.

outputFormat:
A line in the output should appear in response to every 'M' or 'S' entry in FJ's

instructions.

translation:
FJ 想雇佣几个人在他的农场里帮忙，他需要进行很多种操作，请你帮他搞定。

FJ 的农场有 $N$ 块排成一行的田地，编号从 $1$ 到 $N$。每一块田地都有很多草包。FJ 要进行下面几种操作：

1. 给定一段连续的田地，给每一块田地都增加一些新的草包。

2. 给定一段连续的田地，找出草包最少的田地有多少草包。

3. 给定一段连续的田地，统计一共有多少草包。


title: [USACO16JAN] Subsequences Summing to Sevens S

description:
Farmer John's $N$ cows are standing in a row, as they have a tendency to do from time to time.  Each cow is labeled with a distinct integer ID number so FJ can tell them apart. FJ would like to take a photo of a contiguous group of cows but, due to a traumatic  childhood incident involving the numbers $1 \ldots 6$, he only wants to take a picture of a group of cows if their IDs add up to a multiple of 7.

Please help FJ determine the size of the largest group he can photograph.

给你n个数，分别是a[1],a[2],...,a[n]。求一个最长的区间[x,y]，使得区间中的数(a[x],a[x+1],a[x+2],...,a[y-1],a[y])的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。

inputFormat:
The first line of input contains $N$ ($1 \leq N \leq 50,000$).  The next $N$

lines each contain the $N$ integer IDs of the cows (all are in the range

$0 \ldots 1,000,000$).

outputFormat:
Please output the number of cows in the largest consecutive group whose IDs sum

to a multiple of 7.  If no such group exists, output 0.