蓝桥杯——盾神与格子游戏（动态规划+递推）_蓝桥杯算法训练 c语言 盾神与格子游戏

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　在盾神很小很小还不会怎样编程的时候，他迷上了一款风靡一时的双人游戏！游戏双方在地上画n个格子，然后在最后一格放上一颗石头。每人每轮可以把石头向前移动1到3格，最后谁把石头移出第一格就赢了。盾神那时候很傻很天真，每次都是随便乱玩，结果每次都会输。。。
　　盾神今天回想起来，那时候的自己真是弱暴了！！！今天的盾神不仅一眼把这个游戏的必胜方法秒解，还提出了一个进化版：每人每轮不是把石头向前移动1到3格那么简单，而是有m种选择：第i种可以向前移动ai格。其他规则还是和以前一样。那么聪明的你，能告诉盾神，如果双方都采取最优策略，先手第一步该怎样做才可以保证必胜？

输入格式

　　第一行为两个数n，m。
　　第二行m个数，表示ai。

输出格式

　　如果先手必败，输出“poor dun”，否则输出先手第一步应该向前移动多少格，如果有多种方案，选择移动距离最少的那个。

样例输入

6 3
1 10 100

样例输出

10

样例输入

6 3
1 2 3

样例输出

2

样例输入

6 3
1 1 1

样例输出

poor dun

数据规模和约定

　　对于20％的数据，ai为从1到