杜斯特伍德的故事——我们是如何走出死亡并迎来光明

题面与题不符系列 生活

故事背景

是时候走出暗影散播死亡了 题记

这是一个平静的小乡村，至少曾经是。
现今，这里充满了死亡与欺骗的气息，黑夜不再平静，白日不再安宁。
邪恶再次出现在我们中间！并且花样翻新。比以往任何时候都更加强大、背德且无情。
只有全体人的齐心协力，可以拯救杜斯特伍德！（我不是让你们交流啊）

注意事项：

1.我们是古老的国度，所以，我们使用文件输入输出
2.在善恶的角逐中，你必须更快，所以你的时间只有1s
3.黑夜行动必须隐秘，所以允许提供的空间十分狭窄，只有256MB
4.不要忘记文件的密名：jos，virus，phonewire

你准备好了吗
现在
天黑，请闭眼

Day 1

天亮了，请大家睁眼
昨晚是，平安夜。

处于集会中心的村民们大多数都长舒一口气，不过也有人板起了脸，但是大多数人都沉浸在死后余生的兴奋中，无人注意旁边的异动。
这时，主持人领上了一个衣衫褴褛，身上满是伤痕的野孩子。
“这是野孩子，昨晚他选定了自己的榜样，当那位榜样公民死了后，他就会在一怒下变为狼人”似乎永远保持一个语调的主持人说道。
“那快告诉我们那位榜样是谁啊”村民们纷纷地说道。
野孩子顿了顿，开口说道。

（不想看故事的人，题面在下）

“我们的村庄是一个环形，一共有n个屋子，相信各位都知道。昨晚当我来到这里时，我不认识任何人，所以我只好按照一种方法随机选择榜样。虽然我不是你们这里土生土长的人但是我也知道在你们这k是不吉利的，于是我从门牌号为1的屋子开始数，每数k个数就将数到的房屋踢出我的选择序列，于是继续数下去，直到最后只剩下一间房子，于是我就将剩下这间房子的主人选为了我的榜样”。
所有人听完后都吸了一口凉气，没人想象到野孩子会以如此直白的方式同时在好人和狼人前说出来。作为一名守卫，你知道狼人们会在极短的时间内算出这个榜样是谁，并以残忍的方式增加狼人族群的力量——杀掉Ta。你必须，比他们更快。

一句话题面
在1s内算出此死亡循环游戏的最终赢家。

输入格式

一行两个数n,k

输出格式
一行一个数，为榜样的门牌号

样例输入
10 7

样例输出
9

样例解释
野孩子从一号屋开始数，一共有10间屋子，不吉利的数字为7，
排出的顺序依次为7 4 2 1 3 6 10 5 8 9，所以9为最后剩下的数，即榜样

村庄简介
因为杜斯特伍德是一个人类居住的村子，所以门牌号总是从1开始。
对于40%的村庄，它们属于小村镇，n<=1000，k<=1000;
对于100%的村庄，它们可是大城市了，n<=100000000,k<=100000。
不保证榜样为人类，不保证狼人不会自相残杀。

Day 2

黑夜再次来临，由于你上一次的杰出表现，狼人们被迫撤出了村子，居住在村庄周围的野地中。但即使狼人们受到了如此大的挫折，危机仍然迫在眉睫，因为村庄里只剩下最后一位神民(详见狼人杀屠边规则)。
为了扼杀狼人的希望，村民们决定直截了当的进行防卫，筑起火焰之墙。

以下为题面
村庄是由n个哨站和房屋组成的，中间有单向道路连接，但事实上它们完全相同，都防备不了狼人的攻击。
为了避免狼人晚上进行攻击，村民中的纵火者决定直接烧毁村庄外围的房屋(详见扩展版狼人村庄规则)。
时间所剩无几，作为唯一拥有神般计算能力的你，必须贡献一份力！

一句话题面
存在有向图G，删除节点使图不再与外部联通，输出节点数。

输入格式

第一行一个数代表房子数n
第2到n+1行:一个n*n的矩阵，其中若第i行第j列为1，则房子i能直接通往房屋j，若第i行第j列为0，则房屋i不能直接通往房子j

输出格式

一行一个数为纵火犯最少需要烧毁的房屋数

样例输入

12
0 0 1 0 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

样例输出

6

数据范围

对于所有村庄，房间数n<=1000。

Day 3

这次灾变的很多年以后，村庄里健在的人都时常回想起那晚冲天的大火以及狼人在火中的哀嚎，以及每间房子中弥漫的恐惧和无助；自然也不会忘记第二天早晨发觉纵火者成功阻止入侵时所有村民的欢乐。为了彻底根除危机，村民们决定杀死这万恶之源——————狼人的巢穴！；

以下为题面
从村庄到狼人巢穴的路上有着一路艰险，自然也有安全的地方，我们把这个安全的地方称作节点。道路上一共有n个节点，行进时只能从k-1号节点行进至k号节点。在节点中间道路十分崎岖难走，道路崎岖难走的程度取决于节点间海拔的差。
作为先行者，你需要竭尽全力节省村庄的勇士们的体力，于是你决定垫平道路以及垫高节点。
从海拔高为h1的节点垫平至海拔高为h2的节点花费体力为c*abs(h1-h2)，其中c为一个常数。当然，你也可以选择升高节点的海拔，但是这项工作也需要花费一定的体力，具体花费是这样的：每升高x米花费体力为x^2。
由于你是先行者，也是村庄勇士团的成员之一，你必须在铺设道路的过程中尽量减少体力的消耗，以便参加狼人巢穴的那场恶战。为了做好准备，你必须明白你最少要消耗多少体力。

一句话题面
求利用连接和加高操作从1号节点连接到n号节点所需最小花费

输入格式

第一行输入两个数n,c，含义如上
第二行给出n个数，其中第i个数代表第i个节点的初始海拔

输出格式

一行一个数表示最小消耗体力值

样例输入

5 2
2 3 5 1 4

样例输出

15

样例解释

将第四个点垫高到3，花费为4；其余直接连线即可。

数据范围

50%数据n<=1000；
70%数据n<=10000;
100%数据n<=100000;
由于杜斯特伍德处于平原，保证h<=100。