Kumod and Arushi
Kumod and Arushi live in chefland. Government of chefland has decided to gift some money to the citizens of chefland as they are badly affected by demonetisation. All the N citizens of chefland may get equal or unequal amount of money. However some citizen X feels that , he must not get less than a certain amount of the money citizen Y gets. Arushi is the 1st citizen and Kumod is the last i.e. Nth citizen . Kumod always wants to maximize the difference of his and Arushi's money. Is it possible for the government of chefland to keep every citizen satisfied and also maximize the difference of kumod's and Arushi's money.Note: X and Y are different citizens.
First line of input contains two integers N and M, where N is number of citizens and M is the number of relations between some citizen X and Y.
Each of the next M lines contains, three integers X ,Y and Z, where X and Y are some arbitrary citizens and Z is the maximum amount citizen Y can get more than citizen X.
If it is possible to satisfy every citizen and to maximize the difference of Kumod's and Arushi's money.then print POSSIBLE in the first line of output and the next line should contain the maximum difference of Kumod's and Arushi's money. else Output will be NOTPOSSIBLE .
Constraints and subtasks
- 1 ≤ N,M ≤ 10000
- 1 ≤ X,Y ≤ N
- -1000000 ≤ Z ≤ 1000000 Subtask 1: 5 points
- 1 ≤ N ≤ 2
- 1 ≤ M ≤ 2
- -1000000 ≤ Z ≤ 1000000 Subtask 2: 10 points
- 1 ≤ N ≤ 3
- 1 ≤ M ≤ 6
- -1000000 ≤ Z ≤ 1000000 Subtask 3: 85 points
- Original Constraints
Input: 3 3 1 2 5 2 3 7 3 1 5 Output: POSSIBLE 12
Example case 1. Citizen 2 must not get amount 5 more than citizen 1 gets, and citizen 3 must not get amount 7 more than citizen 2, so from these two relations , it's clear that citizen 3 must not get 12 more than citizen 1 . when citizen 3 gets amount 12 more than citizen1 gets, then the last relation that citizen 1 must not get amount 5 more than citizens 3 will be automatically satisfied.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions