# Dramatic chipmunks

0.76 Mr William and Mr Christopher share a beautiful pear tree of a
hybrid Marlowe-Shakes cultivar. It grows right between their
neighbouring farms in Avonford-upon-Strat, an even more beautiful
village in the middle of the English countryside. Alas, that beauty is
marred by the tree's inhabitation by the most despicable and quarrelling
among all zoological species: the dramatic chipmunks.

These mischievous long-toothed chewers spend all day looting the tree's
pears and plotting schemes to steal them from each other. Mr William and
Mr Christopher must put up in martyrdom with their high-pitched
rodent-voiced discussions:

0.24

::: center
![image](dramatic.eps){width="3.3cm"}
:::

*-- Oh, Rosencrantz, thou long-tailed knave! Wherefore doeth thou steal
mine pears?*\
*-- Nay, Guilderstern! Voltemand stole thy pears, that cockered
motley-minded hugger-mugger.*\
*-- Ah, the churlish rascal...And he also stole from that
dismal-dreaming low-classed fustilarian, Laertes!*\
*-- This mustn't be true... Laertes stole from Horatio, and Horatio
stole from Voltemand himself. For nut's sake, this impudent stravaganza
of debauchery shall not be tolerated in this hallowed tree!*\
After all plundering, larceny, and bickering, at the end of the day the
chipmunks indulge in gluttony and consume the fruits of their pillaging
before falling asleep inebriated from their vice.

Can you help Mr William and Mr Christopher figure out how many of their
precious pears fall victims of all this unnecessary daily drama?

## Input

Input consists of several cases. Each case starts with the number of
thefts $n$ and the number of pears $p$ each chipmunk will eat at the end
of the day. Both $n$ and $p$ are between 1 and $10^4$. Follow $n$
triples $s$ $t$ $x$ indicating that $s$ stole $x$ pears from $t$, where
$s$ and $t$ are words made up of between 1 and 20 letters, and $x$ is an
integer between 1 and $10^4$. The robberies are not necessarily given in
chronological order. All chipmunks are at least either the subject or
the object of an *intended* theft.

A chipmunk that steals from another one will be considered of lower
class than the former. Chipmunks acknowledge this classist relationship
transitively, and a higher-class chipmunk should never steal from a
lower-class one. When a chipmunks identifies that it could engage in a
stealing cycle, it will leave the tree before thefts start, to avoid
shaming---even if all other chipmunks are also leaving.

## Output

For each case, print the minimum number of pears that would make it
possible for the described thefts to happen, and still allow for each
chipmunk which did not take part in any cycle to eat (at least) $p$
pears after that.

## Problem information

Author: Edgar Gonzalez

Generation: 2026-01-25T10:14:27.777Z

© *Jutge.org*, 2006--2026.\
<https://jutge.org>
