路终会有尽头，但视野总能看到更远的地方。

    有一些寿司排成一行，每个寿司有一个代号$a[]$，寿司的美味度$d[i,j]$定义为将$i\rightarrow j$一次性取走的价值。每次可以取走一段连续的寿司，获得所有其包含的美味度（如取走$[1,2]$，则累加$d[1,1]+d[2,2]+d[1,2]$），连续一段的美味度不重复计算（以后取寿司不继续累加$d[1,1],d[2,2],d[1,2]$）。取走$c$份代号为$i$的寿司需要付出$mx^2+cx$元，$m$是给定的常数，求可以获得的美味度减去花费的最大值。

    小C现在正要攻打科学馆腹地———计算机第三机房。而信息组的同学们已经建好了一座座堡垒，准备迎战。小C作为一种高度智慧的可怕生物，早已对同学们的信息了如指掌。
    攻打每一个人的堡垒需要一个代价，而且必须攻打若干次才能把镇守之人灭得灰飞烟灭。
    当小C在绞尽脑汁想攻打方案时，突然从XXX的堡垒中滚出来一个纸条：一个惊人的秘密被小C发现了：原来各个堡垒之间会相互提供援助，但是当一个堡垒被攻打时，他对所援助的堡垒的援助就会停止，因为他自己已经自身难保了。也就是说，小C只要攻打某个堡垒一次之后，某些堡垒就只需要花更小的代价攻击了。
    现在，要你求消灭全机房要用掉代价最小多少。

    Grant是一个个体户老板，他经营的小店因为其丰富的优惠方案深受附近居民的青睐，生意红火。小店的优惠方案十分简单有趣。Grant规定：在一次消费过程中，如果您在本店购买了精制油的话，您购买香皂时就可以享受$2.00$元/块的优惠价；如果您在本店购买了香皂的话，您购买可乐时就可以享受$1.50$元/听的优惠价……诸如此类的优惠方案就是说：如果您在本店购买了商品$A$的话，您就可以以$P$元/件的优惠价格购买商品$B$（购买的数量不限）。有趣的是，你需要购买同样一些商品，由于不同的购买顺序，Grant老板可能会叫你付不同数量的钱。比如你需要一块香皂（原价$2.50$元）、一瓶精制油（原价$10.00$元）、一听可乐(原价$1.80$元)，如果你按照可乐，精制油，香皂这样的顺序购买的话，Grant老板会问你要$13.80$元；而如果你按照精制油，香皂，可乐这样的顺序购买的话，您只需付$13.50$元。
现在该村的居民请你编写一个程序，告诉你Grant小店商品的原价，所有优惠方案及所需的商品，计算至少需要花多少钱。不允许购买任何不需要的商品，即使这样做可能使花得钱更少。

    MST（最小生成树）：对于无向带权图，若其导出子图的边权和最小，且原图$V$中对应的任意两个顶点间有且仅有一条通路，则称此图为原图的MST。
    你的任务很简单，对于给定的有向带权图，求出其“最小生成树”，即指定一个根以后，每个点都是从根出发可达的。

    我们已知$n$对夫妻的婚姻状况，称第$i$对夫妻的男方为$B_i$，女方为$G_i$。若某男$B_i$与某女$G_j$曾经交往过（无论是大学，高中，亦或是幼儿园阶段，$i\neq j$），则当某方与其配偶（即$B_i$与$G_i$或$B_j$与$G_j$）感情出现问题时，他们有私奔的可能性。不妨设$B_i$和其配偶$G_i$感情不和，于是$B_i$和$G_j$旧情复燃，进而$B_j$因被戴绿帽而感到不爽，联系上了他的初恋情人$G_k\ldots$一串串的离婚事件像多米诺骨牌一般接踵而至。若在$B_i$和$G_i$离婚的前提下，这$2n$个人最终依然能够结合成$n$对情侣，那么我们称婚姻$i$为不安全的，否则婚姻$i$就是安全的。
    给定所需信息，你的任务是判断每对婚姻是否安全。

    有$N$个男生和$N$个女生，已知每个男生对每个女生的喜欢程度，和每个女生对每个男生的喜欢程度。
    找到一种搭配方式使得总的满意程度最高。

    有$N$位女士和$N$位男士，每位男士或者女士都对对方有个评价。他们会形成$N$对夫妻，如果$A$和$a$结婚，$B$和$b$结婚，但是$A$更偏爱$b$而非$a$而且$b$也更偏爱$A$而非$B$，那么这种婚姻是不稳定的。
    现在要求出当前$N$对的稳定婚姻。

    小N最近在研究NP完全问题，小O看小N研究得热火朝天，便给他出了一道这样的题目：
    有$n$个球，用整数$1$到$n$编号。还有$m$个筐子，用整数$1$到$m$编号。
    每个筐子最多能装$3$个球。
    每个球只能放进特定的筐子中。具体有$e$个条件，第$i$个条件用两个整数$v_i$和$u_i$描述，表示编号为$v_i$的球可以放进编号为$u_i$的筐子中。
    每个球都必须放进一个筐子中。如果一个筐子内有不超过$1$个球，那么我们称这样的筐子为半空的。
    求半空的筐子最多有多少个，以及在最优方案中，每个球分别放在哪个筐子中。
    小N看到题目后瞬间没了思路，站在旁边看热闹的小I嘿嘿一笑：“水题！”
    然后三言两语道出了一个多项式算法。
    小N瞬间就惊呆了，三秒钟后他回过神来一拍桌子：
    “不对！这个问题显然是NP完全问题，你算法肯定有错！”
    小I浅笑：“所以，等我领图灵奖吧!”
    小O只会出题不会做题，所以找到了你——请你对这个问题进行探究，并写一个程序解决此题。

    从前一个和谐的班级，所有人都是搞OI的。有$n$个是男生，有$0$个是女生。男生编号分别为$1,\ldots,n$。

    现在老师想把他们分成若干个两人小组写动态仙人掌，一个人负责搬砖另一个人负责吐槽。每个人至多属于一个小组。

    有若干个这样的条件：第$v$个男生和第$u$个男生愿意组成小组。

    请问这个班级里最多产生多少个小组？

    小R最近遇上了大麻烦，他的程序设计挂科了。于是他只好找程设老师求情。善良的程设老师答应不挂他，但是要求小R帮助他一起解决一个难题。
    问题是这样的，程设老师最近要进行一项邪恶的实验来证明$P=NP$，这个实验一共持续$n$天，第$i$天需要$a[i]$个研究生来给他搬砖。研究生毕竟也是人，所以雇佣研究生是需要钱的，机智的程设老师已经联系好了$m$所大学，第$j$所大学共有$l[j]$个研究生，同时雇佣这所大学的一个研究生需要$p[j]$元钱。
    本来程设老师满心欢喜的以为，这样捡最便宜的$\max\lbrace a[i]\rbrace$个研究生雇来，就可以完成实验；结果没想到，由于他要求硕士生们每天工作$25$个小时不许吃饭睡觉上厕所喝水说话咳嗽打喷嚏呼吸空气，因此一天下来给他搬砖的所有研究生都会进入濒死状态。濒死状态的研究生，毫无疑问，就不能再进行工作了。但是机智的老师早早联系好了$k$家医院，第i家医院医治一个濒死的研究生需要$d[i]$天,并且需要$q[i]$元钱。
    现在，程设老师想要知道，最少花多少钱，能够在这$n$天中满足每天的需要呢？若无法满足，则请输出impossible。注意，由于程设老师良心大大的坏，所以他是可以不把濒死的研究生送去医院的！