{"raw_statement":[{"iden":"statement","content":"The first mafia on planet Earth was actually composed of a bunch of cool jumping monkeys. The name of that group was pretty simple - Monkafia - and they dominated the food chain and the transport systems in the biggest tropical forest of the world at the time. \n\nTha typical Monkafia squadron was composed of a group of m monkeys. They had headquarters - usually composed of two trees. We will call those trees A and B. The monkeys slept on the highest branches of tree A, and, during morning, used to climb down to the lowest branches of tree B, alternating between branches of trees A and B. They could jump multiple times between the two trees.\n\nMonkeys in the Monkafia are very irritating and don't like sharing, so they could never jump on a branch that another monkey had already jumped or been that morning. \n\nWe know that each branch of trees A and B has a certain height, H. It is possible for a monkey to jump from a branch Ga to a branch Gb only if |HGa - HGb| < T, where T is the height a single monkey can jump. \n\nIt is not always possible for two arbitrary trees to have all monkeys of a Monkafia squadron jump down from the topmost branches of one of the trees to the bottommost branches of the other without breaking the rules. Given that, your job here is the following: given a pair o trees, with the heights of their branches and the distance T, find out if it is possible for the squadron to do the morning descend considering all the constraints. Any of the trees can be tree A (the starting tree) or tree B (the ending tree).\n\nThe input begins with four numbers, m, nA, nB e T (1 ≤ m ≤ nA, nB ≤ 500, 1 < T ≤ 108), the number of monkeys, the number of branches in one tree, the number of branches in the other tree and the distance the monkeys can jump. Follow na lines, each with the height of a branch from the first tree (1 ≤ HGa ≤ 108). Then follows nb lines, each with the height of a branch from the second tree (1 ≤ HGb ≤ 108).\n\nAnswer 'S' if it is possible to use that pair of trees and 'N' otherwise.\n\n"},{"iden":"input","content":"The input begins with four numbers, m, nA, nB e T (1 ≤ m ≤ nA, nB ≤ 500, 1 < T ≤ 108), the number of monkeys, the number of branches in one tree, the number of branches in the other tree and the distance the monkeys can jump. Follow na lines, each with the height of a branch from the first tree (1 ≤ HGa ≤ 108). Then follows nb lines, each with the height of a branch from the second tree (1 ≤ HGb ≤ 108)."},{"iden":"output","content":"Answer 'S' if it is possible to use that pair of trees and 'N' otherwise."},{"iden":"examples","content":"Input1 2 2 31321OutputSInput1 2 3 213211OutputSInput2 2 3 213211OutputSInput2 6 7 48452911228312312OutputN"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of webpages, numbered $ 1 $ to $ N $.  \nLet $ K \\in \\mathbb{Z}^+ $ be the maximum number of times a page can be viewed before the user gets annoyed.  \nLet $ G = (V, E) $ be a directed graph where $ V = \\{1, 2, \\dots, N\\} $, and for each page $ i $, there is a directed edge $ i \\to j $ if page $ i $ contains a link to page $ j $.  \nLet $ \\text{visit}(v) \\in \\mathbb{Z}_{\\geq 0} $ denote the number of times page $ v $ has been visited in the current path.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 1 \\leq K \\leq 10^5 $  \n3. For each page $ i \\in V $, the out-degree $ \\deg^+(i) = M_i $, with $ 0 \\leq M_i \\leq N $, and each outgoing link $ j $ satisfies $ 1 \\leq j \\leq N $.  \n4. The user starts at page $ 1 $.  \n5. The user may navigate via:  \n   - Forward: from current page $ u $ to any neighbor $ v $ such that $ (u, v) \\in E $.  \n   - Backward: return to the previous page in the navigation history (modeled as a stack).  \n6. The user gets annoyed upon visiting any page $ v $ for the $ (K+1) $-th time, i.e., if $ \\text{visit}(v) > K $, navigation stops.  \n\n**Objective**  \nFind the maximum number of distinct page views (counting repetitions up to $ K $ times per page) along any valid navigation path starting from page $ 1 $, where navigation follows forward links and the \"back\" button (last-in-first-out history), and no page is visited more than $ K $ times.","simple_statement":"You are given a website with N pages, numbered 1 to N. Page 1 is the homepage. Each page has some links to other pages. A mobile user starts at page 1 and can click links to go forward or press \"back\" to go to the previous page. The user gets annoyed after seeing the same page K times. Find the maximum number of different pages the user can view before getting annoyed.","has_page_source":false}